【leetcode Java】二叉树的递归遍历以及最大深度的求解（Java）

递归是非常神奇的方法，代码看起来很简洁。

对二叉树的遍历和求最大深度可以用递归的方法，主要思路就是遍历左子树，再遍历右子树。如果左子树上面的结点，有右孩子，则调用右子树的方法；遍历到左子树的叶节点的时候，返回，开始遍历右子树。如果右子树上面的结点有左孩子，则调用左子树的方法，遍历到右子树的叶子结点的时候，程序结束。

static void scanNodes(TreeNode root){
        if(root==null){
            return;
        }
        System.out.println(root.val); //先序遍历
        scanNodes(root.left);
        //System.out.println(root.val); 中序遍历
        scanNodes(root.right);
        //System.out.println(root.val); 后序遍历
    }

求二叉树的最大深度，也是这个思路，只需添加个返回值即可

static int getDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=getDepth(root.left);
        int right=getDepth(root.right);
        return left>right?left+1:right+1;
    }

下面附上，完整的测试代码，里面有二叉树结点的定义，大家一看就懂

class  TreeNode
{
    TreeNode left;
    TreeNode right;
    int val;
    TreeNode(int val){
        this.val=val;
    }
    //返回二叉树的深度
    static int getDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=getDepth(root.left);
        int right=getDepth(root.right);
        return left>right?left+1:right+1;
    }

    static void scanNodes(TreeNode root){
        if(root==null){
            return;
        }
        System.out.println(root.val); //先序遍历
        scanNodes(root.left);
        //System.out.println(root.val); 中序遍历
        scanNodes(root.right);
        //System.out.println(root.val); 后序遍历
    }

    public static void main(String[] args)
    {
        TreeNode root=new TreeNode(1);
        TreeNode left1=new TreeNode(2);
        TreeNode left2=new TreeNode(3);
        TreeNode right1=new TreeNode(4);
        //创建一棵树
        root.left=left1;
        left1.right=left2;
        root.right=right1;
        scanNodes(root);
        System.out.println("树的深度是："+getDepth(root));

    }
}

运行结果如下：

1

2

3

4

树的深度是：3