二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />返回它的最大深度 3 

思路:计数器,每递归一次加一,无递归后统计结果,其实就是拆出左树和右树深度取最大值

 public int invertTree(TreeNode root) {
        int depth = 0;
        if(root!=null){
            depth=depth+1;
            int left = depth+invertTree(root.left);
            int right = depth+invertTree(root.right);
            return Math.max(left,right);
        }
        return 0;
    }

官方的解决思路更清晰一些:

public int invertTree(TreeNode root) {
        if(root==null){
            return 0;
        }else {
            int leftDepth = invertTree(root.left);
            int rightDepth = invertTree(root.right);
            return Math.max(leftDepth,rightDepth)+1;
        }
    }

官方思路: max(l,r)+1 l为左树深度,r为右树深度,递归时,每到一层,左右树深度都+1,最终取出最大值+1(根数)

全代码

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
     }
 }
class Solution {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(7);
        TreeNode treeNode2 = new TreeNode(15);
        TreeNode treeNode3 = new TreeNode(20,treeNode2,treeNode1);
        TreeNode treeNode6 = new TreeNode(9,null,null);
        TreeNode treeNode = new TreeNode(3,treeNode6,treeNode3);
        Solution solution = new Solution();
        System.out.println(solution.invertTree(treeNode));
    }
    public int invertTree(TreeNode root) {
        int depth = 0;
        if(root!=null){
            depth=depth+1;
            int left = depth+invertTree(root.left);
            int right = depth+invertTree(root.right);
            return Math.max(left,right);
        }
        return 0;
    }
}