Code More Create

Appearance

Return to top
On this page

55-I.二叉树的深度

题目描述

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

例如：

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

	3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

思路分析

深度优先遍历和广度优先遍历

AC 代码

深度优先遍历

class Solution {
    public int maxDepth(TreeNode root) {
		// base case
        if(root == null) return 0;
		// 获得左右子树的层数，比较大小，取大者，+1
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}

广度优先遍历

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        // 存储每一层的结点
        List<TreeNode> list = new LinkedList<>();
        // 记录深度
        int ans = 0;
        // 添加根节点
        list.add(root);
        // 只要list里面不空，说明该层就有结点
        while(!list.isEmpty()){
            // 存储下一层的结点
            List<TreeNode> tmp  = new LinkedList<>();
            // 遍历该层的结点，如果下一层结点不为null，则加进去
            for(TreeNode node : list){
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            // 层数+1
            ans++;
            // 将list换为下一层的list
            list = tmp;
        }
        return ans;
    }
}