[leetcode]--104. Maximum Depth of Binary Tree

缺乏、安全感 2022-07-11 14:29 116阅读 0赞

Question 104：

> Given a binary tree, find its maximum depth.
> 
> The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
> 
> 中文解释：求二叉树的最大深度

先给出结点的定义：

package leetcode.common;
    
    /** * 树的节点的定义,Use By 104 */
    public class TreeNode { 
        private int val;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(int x) { val = x; }
    
        public int getVal() {
            return val;
        }
    
        public void setVal(int val) {
            this.val = val;
        }
    
        public TreeNode getLeft() {
            return left;
        }
    
        public void setLeft(TreeNode left) {
            this.left = left;
        }
    
        public TreeNode getRight() {
            return right;
        }
    
        public void setRight(TreeNode right) {
            this.right = right;
        }
    }

解决思路：通过递归求二叉树的深度：  
（1）root为空则返回零；  
（2）root非空则返回 1 + （左子树深度 和 右子树深度 的最大值）；

package leetcode;
    
    import leetcode.common.TreeNode;
    import utils.LogUtil;
    
    public class Question104 { 
    
        /** * 用递归做. * @param root * @return */
        public static int maxDepth(TreeNode root) {
            if (root == null) return 0;
            return 1 + Math.max(maxDepth(root.getLeft()), maxDepth(root.getRight())); //isLeaf is checked here
        }
    
        public static void main(String[] args) {
            TreeNode root = new TreeNode(0);
            root.setLeft(new TreeNode(1));
            root.setRight(new TreeNode(2));
    
            TreeNode left1 = root.getLeft();
            left1.setLeft(new TreeNode(3));
    
            LogUtil.log_debug("" + maxDepth(root));
    
        }
    }

这个例子的运行结果：

2017-02-02 12:06:31：3