剑指Offer——二叉树的深度

By AverageJoeWang
 标签:

二叉树的深度

  • 题目描述
    输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

  • 解题思路

    • 直接利用递归的思路对二叉树进行遍历。
    • 根据题目的定义,我们可以用先根次序来遍历二叉树中所有根节点到叶节点的路径,来得到最长的路径就是二叉树的高度。但是这样的代码量较为冗长,我们可以采用递归的方式解决。
    • 我们可以从根节点即左右子树来理解二叉树的深度。对于任意一棵非空二叉树,有如下四种情况:
      • (1)如果一颗树只有一个节点,它的深度是1;
      • (2)如果根节点只有左子树而没有右子树,那么二叉树的深度应该是其左子树的深度加1;
      • (3)如果根节点只有右子树而没有左子树,那么二叉树的深度应该是其右树的深度加1;
      • (4)如果根节点既有左子树又有右子树,那么二叉树的深度应该是其左右子树的深度较大值加1;
  • 代码实现

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return left > right ? (left + 1) : (right + 1);
    }
}