大型门户网站设计公司微信抽奖小程序
题目描述：
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
提示：
- 树中节点的数量在
[0, 104]区间内。 -100 <= Node.val <= 100
上代码，拿去即可运行：
package onlyqi.daydayupgo07.suanfa;import javafx.util.Pair;
import lombok.Data;import java.util.ArrayDeque;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;public class MaxTreeDep {public static void main(String[] args) {TreeNode treeNode1 = new TreeNode(3);TreeNode treeNode2 = new TreeNode(9);TreeNode treeNode3 = new TreeNode(20);TreeNode treeNode4 = new TreeNode(15);TreeNode treeNode5 = new TreeNode(7);TreeNode treeNode6 = new TreeNode(66);treeNode2.setRight(treeNode6);treeNode1.setLeft(treeNode2);treeNode1.setRight(treeNode3);treeNode3.setLeft(treeNode4);treeNode3.setRight(treeNode5);System.out.println(getMaxDep1(treeNode1));}// 广度优先遍历public static Integer getMaxDep1(TreeNode treeNode) {if (Objects.isNull(treeNode)) {return 0;}int maxDep = 1;Queue<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();queue.offer(new Pair<>(treeNode, 1));TreeNode temNode = treeNode;while (!queue.isEmpty()) {Pair<TreeNode, Integer> nodeIntegerPair = queue.poll();maxDep = Math.max(nodeIntegerPair.getValue(), maxDep);Integer dep = nodeIntegerPair.getValue();temNode = nodeIntegerPair.getKey();System.out.println("==============:" + temNode.value);if (temNode.left != null) {queue.offer(new Pair<>(temNode.left, dep + 1));}if (temNode.right != null) {queue.offer(new Pair<>(temNode.right, dep + 1));}}return maxDep;}// 深度优先遍历public static Integer getMaxDep(TreeNode treeNode) {if (Objects.isNull(treeNode)) {return 0;}Stack<Pair<TreeNode, Integer>> stack = new Stack<>();stack.push(new Pair<>(treeNode, 1));int maxDepth = 0;while (!stack.isEmpty()) {Pair<TreeNode, Integer> current = stack.pop();TreeNode currentKey = current.getKey();Integer dep = current.getValue();maxDepth = Math.max(maxDepth, dep);System.out.println("==============:" + currentKey.value);if (!Objects.isNull(currentKey.right)) {stack.push(new Pair<>(currentKey.right, dep + 1));}if (!Objects.isNull(currentKey.left)) {stack.push(new Pair<>(currentKey.left, dep + 1));}}return maxDepth;}
}@Data
class TreeNode {int value;TreeNode left;TreeNode right;public TreeNode(int value) {this.value = value;}
}
运行结果：
慢慢来才是最快的方法--天涯明月 共勉
我要刷300道算法题，第138道 。 希望自己可以坚持下去 。