讨论/《二叉树》 - 二叉树的最大深度/
《二叉树》 - 二叉树的最大深度
共 13 个回复

由于二叉树的天然递归性质,再碰到一些二叉树的题目时,可以先试试递归。
正确写出一个递归程序,只需要两个要素

  1. 终止条件(base case)
  2. 递归逻辑

为了便于理解, 我们先抛开终止条件,看递归逻辑如何确定:

  1. 正确理解函数定义,即函数做了什么事情,不要纠结具体实现方法:
    本题中,函数可以返回以root为根节点的最大深度。将这个函数当做已实现的工具来用
  2. 把上面的函数当做已知工具,组合出你想要的结果
    本题肯定是需要拿函数算出左右节点的深度,看哪个大,加个1就是最终结果

到此,我们可以写出以下内容

public int maxDepth(TreeNode root){
    // 1. 终止条件
    // 2. 递归逻辑
    return Math.max(maxDepth(root.left)+1, maxDepth(root.right)+1);
}

终止条件如何确定?

这个时候回归函数定义,找出递归最小问题,确定返回结果,本题中,当上头让你算一个空节点的最大深度时,你肯定不能再继续交给下面的人算了,因为空间点已经没有左右节点了,这个时候肯定要终止,null的深度肯定还是0咯,返回0就好。
这样一个正确的递归程序就产生了:

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

一行代码足矣:

class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}
9

1,递归

这题最容易想到的就是递归,啥叫“递归”,也就是下面这张图
image.png
开个玩笑,我们画个图来看下
image.png
原理很简单,代码如下

 public int maxDepth(TreeNode root) {
        return root==null? 0 : Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }

运行时间
image.png

2,BFS

BFS的实现原理就是一层层遍历,统计一下总共有多少层,我们来画个图分析一下。
image.png
代码如下

    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        //创建一个队列
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        int count = 0;
        while (!deque.isEmpty()) {
            //每一层的个数
            int size = deque.size();
            while (size-- > 0) {
                TreeNode cur = deque.pop();
                if (cur.left != null)
                    deque.addLast(cur.left);
                if (cur.right != null)
                    deque.addLast(cur.right);
            }
            count++;
        }
        return count;
    }

我们再来看一下运行时间,显然效率不是很高
image.png

3,DFS

我们可以使用两个栈,一个记录节点的stack栈,一个记录节点所在层数的level栈,stack中每个节点在level中都会有一个对应的值,并且他们是同时出栈,同时入栈

    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        //stack记录的是节点,而level中的元素和stack中的元素
        //是同时入栈同时出栈,并且level记录的是节点在第几层
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> level = new Stack<>();
        stack.push(root);
        level.push(1);
        int max = 0;
        while (!stack.isEmpty()) {
            //stack中的元素和level中的元素同时出栈
            TreeNode node = stack.pop();
            int temp = level.pop();
            max = Math.max(temp, max);
            if (node.left != null) {
                //同时入栈
                stack.push(node.left);
                level.push(temp + 1);
            }
            if (node.right != null) {
                //同时入栈
                stack.push(node.right);
                level.push(temp + 1);
            }
        }
        return max;
    }

运行结果
image.png


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

5

解题思路

递归法,从下到上,后续遍历。
每完成一层,取左右子树深度最大的值,完成一层要加1。
时间复杂度O(n),空间复杂度O(1)。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     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 int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left_dept = maxDepth(root.left);
        int right_dept = maxDepth(root.right);
        return Math.max(left_dept,right_dept) +1;
    }
}
3

c++
dfs简单解决,但是效率不高。

class Solution {
public:
    vector<int> ans;
    void dfs(TreeNode* s,int count=1)
    {
        if(s->left==NULL&&s->right==NULL)
        {
            ans.push_back(count);
            return;
        }

        if(s->left!=NULL)
        {
            dfs(s->left,count+1);
        }

        if(s->right!=NULL)
        {
            dfs(s->right,count+1);
        }

    }

    int maxDepth(TreeNode* root) 
    {
        if(root==NULL) return 0;
        dfs(root);
        int max=0;
        for(int i=0;i<ans.size();i++)
        {
            cout<<ans[i]<<" ";
            if(ans[i]>max) max=ans[i];
        }
        return max;
    }
};
2

python 实现

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # 自顶向下
        Solution.answer = 0
        def depth(root, d):
            if not root: return 
            if not root.left and not root.right:
                Solution.answer = max(Solution.answer, d)
            depth(root.left, d+1)
            depth(root.right, d+1)
        
        depth(root, 1)
        return Solution.answer

        # 自底向上
        # def maxDep(root):
        #     if not root: return 0
        #     return max(maxDep(root.left), maxDep(root.right)) + 1
        # index = maxDep(root)
        # return index


        # 层次遍历改版
        # index = 0
        # if not root: return 0
        # queue = [root]
        # while queue:
        #     index += 1
        #     for i in range(len(queue)):
        #         cur_node = queue.pop(0)
        #         if cur_node.left:
        #             queue.append(cur_node.left)
        #         if cur_node.right:
        #             queue.append(cur_node.right)
        # return index
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans = 0;
    public int maxDepth(TreeNode root) {
        ans = fun(root);
        return ans;
    }
    //自底向上
    public int fun(TreeNode root){
        if(root==null){
            return 0;
        }
        int left = fun(root.left)+1;
        int right = fun(root.right)+1;
        return Math.max(left,right);
    }

    //自顶向下
    // public void fun(TreeNode root,int k){
    //     if(root==null){
    //         return;
    //     }
    //     //到底了

    //         ans = Math.max(ans,k);
        
    //     fun(root.left,k+1);
    //     fun(root.right,k+1);
    // }
}

求助下大家,我用 Python 自顶向下的方法实现的,在控制台输入 [1,null,2] 这个用例,输出 2,结果和答案一致;但是在提交时,有个测试用例也是 [1,null,2],但是却判断我的输出结果是 3,非常奇怪,因为我自己本地调试了,结果也是 2,不知道为什么用 leetcode 输出jie'guo 是 3

下面是我的代码:

class Solution:
    ans = -1
    def max_core(self, root, depth):
        if not root: return
        if root.left is None and root.right is None:
            Solution.ans = max(Solution.ans, depth)
            return
        self.max_core(root.left, depth+1)
        self.max_core(root.right, depth+1)
    
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        depth = 1
        self.max_core(root, depth)
        
        return Solution.ans

希望能有大佬帮忙解答下,不胜感激!

C++求最大深度递归写法:

    int maxDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;           // 遇到叶结点,则叶结点的深度为0
        }
        int leftDepth = maxDepth(root->left);       // 左子树深度
        int rightDepth = maxDepth(root->right);     // 右子树深度
        return max(leftDepth,rightDepth)+1;         // 返回当前结点的深度,当前结点的深度等于左子树和右子树中的最大值,再+1
    }

递归求树深度

使用成员变量保存最大深度,每一次递归时非空则对比深度,并继续左右子树的递归。

class Solution {
    int maxDep = 0;
    public int maxDepth(TreeNode root) {
        walk(root,0);
        return maxDep;
    }
    public void walk(TreeNode root,int dep){
        if(root==null){
            maxDep = Math.max(dep,maxDep);
            return;
        }
        dep++;
        walk(root.left,dep);
        walk(root.right,dep);
    }
}