二叉树最大深度和最小深度
LeetCode 104. 二叉树的最大深度
LeetCode 111. 二叉树的最小深度
是两道和树深度相关的题目
最大深度分析
从根节点分析：
1）如果根节点就是空节点，则最大深度就是 0
2）如果根节点的左子节点且右子节点是空节点，那么最大深度就是 1
3）如果根节点的左子节点不为空，右子节点为空，则计算左子树的最大深度
4）如果根节点的右子节点不为空，左子节点为空，则计算右子树的最大深度
5）如果根节点的左子节点和右子节点都不是空节点，则需要依次计算左子树和右子树的最大深度，取两者最大值
public static int maxDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}if (root.left != null && root.right != null) {return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}if (root.left != null && root.right == null) {return maxDepth(root.left) + 1;}if (root.left == null && root.right != null) {return maxDepth(root.right) + 1;}}
可是上述方法怎么结束呢？
其实只要根节点的左子节点不为空，则需要计算左子节点的最大深度
同理只要根节点的右子节点不为空，则需要计算右子节点的最大深度
public static int maxDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}int maxLeft;int maxRight;if (root.left != null) {maxLeft = maxDepth(root.left);}if (root.right != null) {maxRight = maxDepth(root.right);}return Math.max(maxLeft, maxRight) + 1;}
可是若 root.left == null 会导致 maxLeft 不能被初始化
同理若 root.right == null 会导致 maxRight 不能被初始化
会导致 Math.max(maxLeft, maxRight) + 1 编译报错
那 maxLeft 和 maxRight 可以怎么初始化呢？
可以初始化一个比较小的值，然后和 maxDepth 结果比较并取较大值
public static int maxDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}int maxLeft = Integer.MIN_VALUE;int maxRight = Integer.MIN_VALUE;if (root.left != null) {maxLeft = Math.max(maxDepth(root.left), maxLeft);}if (root.right != null) {maxRight = Math.max(maxDepth(root.right), maxRight);}return Math.max(maxLeft, maxRight) + 1;}
若不加 if (root.left != null) 会怎么样？
若 root.left == null 为怎么样？
maxDepth(root.left) 会再执行一次，但是因为 root.left == null ，所以直接返回 1 ，Math.max(maxDepth(root.left), maxLeft) 结果还是 1 ，
即 int maxLeft = maxDepth(root.left)
同理 int maxRight = maxDepth(root.right)
public static int maxDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}int maxLeft = maxDepth(root.left);int maxRight = maxDepth(root.right);return Math.max(maxLeft, maxRight) + 1;}
可以再优化一下，无需判断 root.left == null 或 root.right == null
最大深度完整算法
public static int maxDepth(TreeNode root) {if (root == null) {return 0;}int maxLeft = maxDepth(root.left);int maxRight = maxDepth(root.right);return Math.max(maxLeft, maxRight) + 1;}
最小深度分析
从根节点分析：
1）如果根节点就是空节点，则最小深度就是 0
2）如果根节点的左子节点且右子节点是空节点，那么最小深度就是 1
3）如果根节点的左子节点不为空，右子节点为空，则计算左子树的最小深度
4）如果根节点的右子节点不为空，左子节点为空，则计算右子树的最小深度
5）如果根节点的左子节点和右子节点都不是空节点，则需要依次计算左子树和右子树的最小深度，取两者最小值
public static int minDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}if (root.left != null && root.right != null) {return Math.min(minDepth(root.left), minDepth(root.right)) + 1;}if (root.left != null && root.right == null) {return minDepth(root.left) + 1;}if (root.left == null && root.right != null) {return minDepth(root.right) + 1;}}
可是上述方法怎么结束呢？
其实只要根节点的左子节点不为空，则需要计算左子节点的最小深度
同理只要根节点的右子节点不为空，则需要计算右子节点的最小深度
public static int minDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}int minLeft;int minRight;if (root.left != null) {minLeft = minDepth(root.left);}if (root.right != null) {minRight = minDepth(root.right);}return Math.min(minLeft, minRight) + 1;}
可是若 root.left == null 会导致 minLeft 不能被初始化
同理若 root.right == null 会导致 minRight 不能被初始化
会导致 Math.min(minLeft, minRight) + 1 编译报错
那 minLeft 和 minRight 可以怎么初始化呢？
可以初始化一个比较大的值，然后和 minDepth 结果比较并取较小值
public static int minDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}int minLeft = Integer.MAX_VALUE;int minRight = Integer.MAX_VALUE;if (root.left != null) {minLeft = Math.min(minDepth(root.left), minLeft);}if (root.right != null) {minRight = Math.min(minDepth(root.right), minRight);}return Math.min(minLeft, minRight) + 1;}
可以再优化一下
最小深度完整算法
public static int minDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}int min = Integer.MAX_VALUE;if (root.left != null) {min = Math.min(minDepth(root.left), min);}if (root.right != null) {min = Math.min(minDepth(root.right), min);}return min + 1;}