剑指offer系列之三十七：二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

有了前面寻找二叉树路径的基础之后，解决这题应该不难。根据书上的思路，有一种更简洁的算法，思路如下：如果二叉树只有根节点那么深度就是1，如果只有左子树，那么就是左子树的深度加1就是整棵二叉树的深度；如果只有右子树，那么二叉树的深度就是右子树的深度加1；如果既有左子树又有右子树，那么二叉树的深度就是左右子树中深度更大的深度加1了。根据这个过程，自然发现，实际上只需要分别递归二叉树的左右子树并计算其深度，那么最后在其较大值中加1就是二叉树的深度了。所以，实现的代码如下（已被牛客AC）：

package com.rhwayfun.offer;

public class BTreeDepth {

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    public int TreeDepth(TreeNode root) {
        if(root == null) return 0;
        int leftSubTree = TreeDepth(root.left);
        int rightSubTree = TreeDepth(root.right);
        return leftSubTree > rightSubTree ? leftSubTree + 1 : rightSubTree + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(6);
        TreeNode node6 = new TreeNode(7);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.right = node5;
        node4.left = node6;

        int d = new BTreeDepth().TreeDepth(root);
        System.out.println(d);
    }
}