1、104 二叉树的最大深度 559 n叉树的最大深度
-
104 二叉树的最大深度
-
递归法
-
本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
-
根节点的高度就是二叉树的最大深度，本题中通过后序求的根节点高度来求的二叉树最大深度。
-
代码
class Solution { public int maxDepth(TreeNode root) { return getDepth(root); } public int getDepth(TreeNode node) { if(node == null) { return 0; } int leftDepth = getDepth(node.left); int rightDepth = getDepth(node.right); int depth = Math.max(leftDepth, rightDepth) + 1; return depth; } }
-
-
迭代（层序遍历）
class Solution { public int maxDepth(TreeNode root) { int depth = 0; Deque<TreeNode> queue = new ArrayDeque<>(); if(root!=null) { queue.offerLast(root); } while(!queue.isEmpty()) { depth ++; int size = queue.size(); for(int i=0; i<size; i++ ) { TreeNode node = queue.pollFirst(); if(node.left != null) { queue.offerLast(node.left); } if(node.right != null) { queue.offerLast(node.right); } } } return depth; } }
-
-
599 n叉树的最大深度
-
递归法
class Solution { public int maxDepth(Node root) { return getHeight(root); } public int getHeight(Node node) { if(node == null) { return 0; } int maxChildHeight = 0; for(int i=0; i<node.children.size(); i++) { int childHeight = getHeight(node.children.get(i)); maxChildHeight = Math.max(maxChildHeight,childHeight); } int height = maxChildHeight+1; return height; } } -
迭代法（层序遍历）
class Solution { public int maxDepth(Node root) { int depth = 0; Deque<Node> queue = new ArrayDeque<>(); if(root!=null) { queue.offerLast(root); } while(!queue.isEmpty()) { int size = queue.size(); depth++; for(int i=0; i<size; i++) { Node node = queue.pollFirst(); for(int j=0; j<node.children.size(); j++) { queue.offerLast(node.children.get(j)); } } } return depth; } }
-
2、111 二叉树的最小深度
-
递归法
- 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
- 反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
- 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。
class Solution { public int minDepth(TreeNode root) { return getDepth(root); } public int getDepth(TreeNode node) { if(node == null){ return 0; } int leftDepth = getDepth(node.left); int rightDepth = getDepth(node.right); if(node.left == null && node.right != null){ return rightDepth + 1; } if(node.left != null && node.right == null){ return leftDepth + 1; } int depth = 1 + Math.min(leftDepth, rightDepth); return depth; } } -
迭代法（层序遍历）
- 只有当左右孩子都为空的时候，才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点
class Solution { public int minDepth(TreeNode root) { int depth = 0; Deque<TreeNode> queue = new ArrayDeque<>(); if(root!=null) { queue.offerLast(root); } while(!queue.isEmpty()) { int size = queue.size(); depth++; for(int i=0; i<size; i++) { TreeNode node = queue.pollFirst(); if(node.left ==null && node.right == null) { return depth; } if(node.left!=null) { queue.offerLast(node.left); } if(node.right!=null) { queue.offerLast(node.right); } } } return depth; } }
3、222 完全二叉树的节点个数
-
递归法
-
类似于 104 二叉树的最大高度
-
递归遍历顺序：从下往上 ==》 后序遍历：左右中
-
递归三部曲
- 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
- 确定终止条件：如果为空节点的话，就返回0，表示节点数为0。
- 确定单层递归的逻辑：先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
-
代码
class Solution { public int countNodes(TreeNode root) { return getCount(root); } public int getCount(TreeNode node) { if(node == null) { return 0; } int leftCount = getCount(node.left); int rightCount = getCount(node.right); int count = leftCount + rightCount + 1; return count; } }
-
-
迭代法（层序遍历）
class Solution { public int countNodes(TreeNode root) { int count = 0; Deque<TreeNode> queue = new ArrayDeque<>(); if(root != null) { queue.offerLast(root); } while(!queue.isEmpty()) { int size = queue.size(); for(int i=0; i<size; i++) { TreeNode node = queue.pollFirst(); count++; if(node.left != null) { queue.offerLast(node.left); } if(node.right != null) { queue.offerLast(node.right); } } } return count; } }