【二叉树专题】剑指 Offer 55 – I. 二叉树的深度-跟着帅地玩副业，开拓第二曲线PlayOffer

糖香香普通 2023年7月2日下午3:26

       class Solution {
       //递归
        public int maxDepth(TreeNode root) {
            TreeNode head = root;
            if (head == null) return 0;
            if (head.left == null && head.right == null) return 1;
            int leftNum = maxDepth(head.left);
            int rightNum = maxDepth(head.right);
            return Math.max(leftNum,rightNum)+1;
        }
    }

0 赞同 0 条回复

宁永久会员 2023年3月10日上午9:47

递归实现

class Solution {
    public int maxDepth(TreeNode root) {
        //递归实现
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月3日下午2:40

递归题目，优先考虑当前函数的功能能否为自己所服用，可以，就形成递归。

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

0 赞同 0 条回复

PatNick 普通 2022年12月19日下午6:25

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
        # 没有左右孩子,到叶子节点了
            return 0

        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left,right) + 1

0 赞同 0 条回复

如梦似歌普通 2022年12月11日下午4:45

/**
 * 复杂度分析:
 * 时间复杂度: T(n) = O(n) 我们需要进行n次递归调用，其中n是二叉树中的结点数
 * 空间复杂度: S(n) = O(d) 对于每次递归，我们需要在递归调用栈中保存递归函数的参数和局部变量的值。如果树的深度为d，则调用栈的深度也为d
 */
class Solution {
    public int maxDepth(TreeNode root) {
        int m; //m用来记录左子树的深度
        int n; //n用于记录右子树的深度
        if(root  null){
            return 0;  //如果树为空，则返回0
        }
        //否则递归计算左子树深度m，递归计算右子树深度n，最后树的深度为m和n中较大者加1
        m = maxDepth(root.left);
        n = maxDepth(root.right);
        return m > n ? m+1 : n+1;
    }
}

1 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:05

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //使用层序，或递归
        queue<TreeNode*> que;
        if(root==nullptr) return 0;
        que.push(root);
        int deepth = 0;
        while(!que.empty()){
            int size = que.size();
            deepth++;
            for(int i = 0; i < size;i++){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return deepth;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2022年11月18日下午1:51

C++递归

“`c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
if(root != NULL &&(root->left == NULL && root->right == NULL)) return 1;
return max(maxDepth(root->right)+1, maxDepth(root->left)+1);
}
};
“`

0 赞同 0 条回复

cute. 普通 2022年11月12日上午9:51

思路：递归

var maxDepth = function(root) {
    if (root == null) return 0;
    let left = maxDepth(root.left);
    let right = maxDepth(root.right);
    return Math.max(left, right) + 1;
};

● 时间复杂度：O(n)
● 空间复杂度: O(n)

0 赞同 0 条回复

xye 普通 2022年11月11日下午9:41

时间O(n)空间O(n)

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    return Max(left, right) + 1
}

func Max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

0 赞同 0 条回复

symbol 普通 2022年11月7日上午9:30

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left) //遍历左子树
    right := maxDepth(root.Right) //遍历右子树
    return max(left, right) + 1
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

时间复杂度：O(n)，其中 nn 为二叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度：O(height)，其中height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

0 赞同 0 条回复

潜行1 我是火车王！普通 2022年11月3日下午11:38

时间O(N) 空间 O(N)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */


func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    return maxInt(maxDepth(root.Left), maxDepth(root.Right)) + 1

}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

0 赞同 0 条回复

星河普通 2022年11月3日下午8:51

DFS后序：
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}
时间O(N)，空间O(N)
BFS层序
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
        int res = 0;
        while(!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }
}
时间O(N)，空间O(N)

0 赞同 0 条回复

Asphyxia 普通 2022年11月1日下午10:18

dfs或bfs均可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> q;
        if(root!=NULL) q.push(root);
        TreeNode* cur = root;
        int depth = 0;
        while(!q.empty()){
            int s = q.size();
            for(int i=0;i<s;i++){
                cur = q.front();
                q.pop();
                if(cur->left){
                    q.push(cur->left);
                }
                if(cur->right){
                    q.push(cur->right);
                }
            }
            depth++;
        }
        return depth;
    }
};

0 赞同 0 条回复

一只骆驼普通 2022年11月1日下午8:57

递归

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

0 赞同 0 条回复

cxxz 普通 2022年11月1日下午4:54

后序遍历，函数功能是返回节点深度，关系式当前节点深度等于左右子树深度最大值+1，base是节点为null时深度为0。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) 
            return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return max(left, right) + 1;
    }
};

0 赞同 0 条回复

优秀市民普通 2022年11月1日上午12:26

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if(not root):
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return left +1 if left > right else right + 1

使用树的后续遍历，然后递归执行
时间复杂度on
空间复杂度on

0 赞同 0 条回复

晨普通 2022年10月31日下午9:57

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 后序遍历
        if root == None:
            return 0
        left_height = self.maxDepth(root.left)
        ringht_height = self.maxDepth(root.right)
        return max(left_height, ringht_height) + 1

        # # 层序遍历
        # if root == None:
        #     return 0
        # queue = [root]
        # res = 0
        # tmp = []

        # while queue:
        #     tmp = []
        #     for node in queue:
        #         if node.left:
        #             tmp.append(node.left)
        #         if node.right:
        #             tmp.append(node.right)
        #     queue = tmp
        #     res += 1
        # return res

时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

马啸天永久会员 2022年10月31日下午2:48

 public int maxDepth(TreeNode root) {

        //1.先找到结束条件
        if (root == null)
            return 0;
        //2.找到问题的递归等价关系式
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }

0 赞同 0 条回复

晨渊普通 2022年10月31日上午11:18

class Solution {
public:
    int maxDepth(TreeNode* root) {

        //递归出口
        if(root == NULL ) return 0;
        else if(root->left == NULL && root->right == NULL)  return 1;
        else return max(maxDepth(root->left),maxDepth(root->right))+1;

    }
};

时间复杂度O(logN)和O(n)之间
空间复杂度O(n)

0 赞同 0 条回复

刺猬普通 2022年10月30日下午7:30

DFS

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr)
            return 0;
        return max(maxDepth(root->left) , maxDepth(root->right)) + 1;
    }
};

时间复杂度O(N)
空间复杂度O(height) height为二叉树的高度

0 赞同 0 条回复

Ruby🗽 普通 2022年10月30日下午5:46

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

时间复杂度On
空间复杂度O(height)

0 赞同 0 条回复

Chin 普通 2022年10月30日下午2:50

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

时间复杂度On
空间复杂度O(height）

0 赞同 0 条回复

cxc 普通 2022年10月30日下午2:34

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        //左子树和右子树最大深度+1
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

0 赞同 0 条回复

云雾里普通 2022年10月30日下午2:17

//BFS后序
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
    //DFS最大层数
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        List<TreeNode> queue = new LinkedList<TreeNode>() {{ add(root); }}, tmp;
        int res=0;
        while (!queue.isEmpty()){
            tmp=new LinkedList<>();
            for (TreeNode treeNode : queue) {
                if(treeNode.left!=null)tmp.add(treeNode.left);
                if(treeNode.right!=null)tmp.add(treeNode.right);
            }
            queue=tmp;
            res++;
        }
        return res;
    }

0 赞同 0 条回复

小肸永久会员 2022年10月30日下午1:17

思路一：递归。递归的终止条件是当节点等于null，返回0。递归函数的返回参数类型是int型，因为深度是一个数字，注意二叉树的深度是从上往下算，高度是从下往上算。递归函数的返回值为二叉树左子树、右子树两个深度的最大值。时间复杂度为O(N)，N为树的节点个数，空间复杂度为O(height)，递归需要栈空间，递归多少次取决于树的高度。

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

思路二：利用层次遍历的思想，求有多少层，深度就为多少。时间复杂度O(N)，空间复杂度取决于队列存储的元素个数。用了一个队列，但队列大部分情况下不会存储树中全部节点。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int res = 0;
        Queue queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            for (int i = 0; i < count; i ++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res ++;
        }
        return res;
    }
}

0 赞同 0 条回复

酥合普通 2022年10月29日下午8:58

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(null == root) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

    }
}

时间：O(n)
空间：O(n)

0 赞同 0 条回复

猫猫真可爱普通 2022年10月29日下午7:10

递归或者层次遍历

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

0 赞同 0 条回复

阿白普通 2022年10月29日下午3:26

后序递归遍历，左右子树高者为父节点高度
时间O（n），空间O（1）

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr)
            return 0;
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        return std::max(l, r) + 1;
    }
};

0 赞同 0 条回复

派大星普通 2022年10月29日下午2:21

class Solution {
//使用递归的方法，递归结束的条件为空，输出结果为左子树的高度和右子树的高度比较最大值加一
//时间复杂度O(n)
//空间复杂度O(n)
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int liftmax = 1;
        int rightmax = 1;
        liftmax += maxDepth(root.left);
        rightmax += maxDepth(root.right);

        return (liftmax>=rightmax ?liftmax:rightmax);
    }
}

0 赞同 0 条回复

@ 普通 2022年10月29日上午10:56

思路：用递归的方式来进行深度优先搜索
时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;

        int rl = maxDepth(root.left) + 1;
        int rr = maxDepth(root.right) + 1;

        return rl >= rr ? rl : rr;


    }
}

0 赞同 0 条回复

鸿渐普通 2022年10月29日上午10:00

/**
     * 深度优先搜索
     * @param root
     * @return
     */

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


    /**
     * 层序遍历 广度优先搜索
     * @param root
     * @return
     */
    public static int maxDepth2(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int res = 0;
        while (!queue.isEmpty()) {
            res++;
            int n = queue.size();

            //每一层的节点都遍历一次，并且从队列中取出，当到达最后一层的时候，队列的元素不会再新增，所以此时就可以结束循环
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return res;
    }

0 赞同 0 条回复

Gg 普通 2022年10月28日下午11:50

class Solution {
    // 递归深度遍历
    // 本质上为利用栈进行保存，空间复杂度O(n)
    // 只遍历每一节点，时间复杂度为O(n)
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

0 赞同 0 条回复

天然普通 2022年10月28日下午10:36

学习新思路，做好每道题
递归思路还是不好想，用的是左右结点存储遍历，返回深度时间复杂度O(n),空间复杂度O(n)

#方法1：
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0 
        num,res = [root],0
        while num:
            tem =[]
            for k in num:
                if k.left: tem.append(k.left)
                if k.right:tem.append(k.right)
            num = tem
            res+=1
        return res
方法2：递归
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

0 赞同 0 条回复

狗蛋儿普通 2022年10月28日下午9:41

class Solution {
public:
    int res;
    //后序遍历 利用高度代替深度 
    //左右中方式 从底部向上进行遍历
    //这个时候我们可以积累depth的值，找最大返回
    int maxdepth(TreeNode* pRoot){
        if(pRoot == nullptr) return 0;
        int leftDepth = maxdepth(pRoot->left);
        int rightDepth = maxdepth(pRoot->right);
        int depth = 1 + max(leftDepth,rightDepth);
        return depth;
    }
    //前序遍历 利用回溯的方式，
    //中左右，自上而下，自左向右
    //每一次都是找到叶子节点，然后进行计算
    void maxdepth(TreeNode* pRoot,int depth){
        res = res > depth ? res:depth;
        if(pRoot->left == nullptr && pRoot->right == nullptr) return;
        if(pRoot->left){
            depth++;
            maxdepth(pRoot->left,depth);
            depth--;
        }
        if(pRoot->right){
            depth++;
            maxdepth(pRoot->right,depth);
            depth--;
        }
        return ;
    }
    int TreeDepth(TreeNode* pRoot) {
        res =0;
        if(pRoot == nullptr) return 0;
        maxdepth(pRoot,1);
        return res;
    }
};

0 赞同 0 条回复

单个酒窝儿普通 2022年10月28日下午8:50

1、运用递归求左子树和右子树的二叉树深度，求最大值并+1

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        return max(maxDepth(root->left),maxDepth(root->right)) + 1;
    }
};

0 赞同 0 条回复

感到自己好渺小普通 2022年10月28日下午7:25

class Solution {
    public int maxDepth(TreeNode root) {
            //递归解法(DFS)
            //求一棵二叉树的深度可以分解成1(根节点)+左右子树的最大深度
            //求左右子树的深度可以分解成1(左右子树的根节点)+左右子树的左右子树的深度
            //依次类推，直到遇见叶子结点，它的左右子树均为空,深度为0，return 0;这也是递归的终止条件
            if(root == null) return 0;   //递归终止条件
            int leftDepth = maxDepth(root.left);  //左子树的深度
            int rightDepth = maxDepth(root.right);  //右子树的深度
            return Math.max(leftDepth,rightDepth)+1;    //1为根结点点的深度
    }
}
时间复杂度：O(n)   因为需要遍历二叉树中的n个节点
空间复杂度：O(n)   最坏情况(当二叉树退化成链表）时，递归深度为n层

0 赞同 0 条回复

Haoyun 普通 2022年10月28日下午6:29

var maxDepth = function(root) {
  if(!root) {
      return 0;
  } else {
      let leftDepth = maxDepth(root.left);
      let rightDepth = maxDepth(root.right);
      return Math.max(leftDepth, rightDepth) + 1;
  }

};

时间：O(n)

0 赞同 0 条回复

T 普通 2022年10月28日下午4:49

递归版本

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) 
            return 0;

        return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
    }
}

0 赞同 0 条回复

虾仁猪心普通 2022年10月28日下午3:51

使用递归的思路

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

0 赞同 0 条回复

mpweixin用户永久会员 2022年10月28日下午3:43

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

//思路：递归思想，三部曲

0 赞同 0 条回复

庄重普通 2022年10月28日下午3:16

// 思路：用递归来做
//     1.函数功能：计算二叉树深度
//     2.关系式：max(lDepth,rDepth) + 1
//     3.初始值 if(root == NULL) return 0
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;

        int lDepth = maxDepth(root->left);
        int rDepth = maxDepth(root->right);

        return max(lDepth,rDepth) + 1;

    }
};
//时间复杂度:O(logn)
//空间复杂度:O(n)

0 赞同 0 条回复

wxc 普通 2022年10月28日上午10:43

额

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None :
            return 0
        else:
            l = self.maxDepth(root.left)
            r = self.maxDepth(root.right)
            return max(l,r)+1

0 赞同 0 条回复

你有点可爱喔普通 2022年10月28日上午10:37

思路：深度优先，自底向上。时间复杂度O(n)，空间复杂度O(n)

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

0 赞同 0 条回复

追普通 2022年10月28日上午9:36

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

深度优先：采用递归的思想，树的深度为1+max(左子树深度，右子树深度)

0 赞同 0 条回复

黎昕普通 2022年10月28日上午12:50

深搜

时间O(n)
空间O(n)

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        else{
            int left=maxDepth(root->left)+1;
            int right=maxDepth(root->right)+1;
            return left>right?left:right;
        }
    }
};

0 赞同 0 条回复

浅夏的无奈普通 2022年10月27日下午11:53

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }else{
            int leftMax = maxDepth(root.left);
            int rightMax = maxDepth(root.right);
            return Math.max(leftMax,rightMax)+1;
        }

    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年10月27日下午11:52

方法1：深度优先，使用递归思想，树的深度=1+max(左子树的深度，右子树的深度),时间复杂度：O(n),空间复杂度O(height)
方法2：广度优先，使用队列，找到每层的所有节点，当当前层的节点数为0时，结束循环，返回计数深度，时间复杂度O(n)，空间复杂度O(n）

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # 深度优先搜索
        # if root is None:
        #     return 0
        # else:
        #     left_depth = self.maxDepth(root.left)
        #     right_depth = self.maxDepth(root.right)
        #     return max(left_depth, right_depth) + 1

        # 广度优先搜索
        queue,res = [root],0
        if not root:
            return 0
        while queue:
            temp = []
            for node in queue:
                if node.left:
                    temp.append(node.left)
                if node.right:
                    temp.append(node.right)
            queue = temp
            res += 1
        return res

0 赞同 0 条回复

Y7n05h 普通 2022年10月27日下午10:32

class Solution {
    int depth;
    void maxDepth(TreeNode *root, int layer) {
        if (!root) return;
        maxDepth(root->left, layer + 1);
        maxDepth(root->right, layer + 1);
        if (layer > depth) depth = layer;
    }

public:
    int maxDepth(TreeNode *root) {
        if (!root) return 0;
        depth = 0;
        maxDepth(root, 1);
        return depth;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月27日下午10:31

递归

/**
递归
时间复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度：O(height)，其中height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right) + 1;
    }
}

层次遍历

/**
利用队列进行层次遍历
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        Deque<TreeNode> queue = new LinkedList<>();
        int depth = 0;
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode cur = queue.poll();
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
            depth++;
        }
        return depth;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年10月27日下午10:26

递归思路，定义两个变量分别记录左子树和右子树，
时间O(n)
空间O(n)

class Solution {

    public int maxDepth(TreeNode root) {
        if(root == null)    return 0;

        int a = maxDepth(root.left)+1;
        int b = maxDepth(root.right)+1;
        return Math.max(a,b);
    }  
}

0 赞同 0 条回复

Error 普通 2022年10月27日下午10:23

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack = [root]

        res = 0
        while stack:
            res += 1
            for i in range(len(stack)):
                node = stack.pop(0)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        return res

时间复杂度 O(n)

0 赞同 0 条回复

青木普通 2022年10月27日下午10:10

// 将这个函数看作返回这颗树的深度，如果root为空返回0， 如果root没有子节点返回1，
 // 都不是的话就返回子树的最深的深度，并加上自己这一层的深度
 // 时间复杂度O(n)
 // 空间复杂度O(n)
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null && root.right == null){
            return 1;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

0 赞同 0 条回复

绍熙普通 2022年10月27日下午9:49

树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；

常见的 DFS ：先序遍历、中序遍历、后序遍历；
常见的 BFS ：层序遍历（即按层遍历）

class Solution {
    public int maxDepth(TreeNode root) {

        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年10月27日下午9:04

public int maxDepth(TreeNode root) {
        // 1. 结束条件
        if (root == null) {
            return 0;
        }

        // 2. 等价关系式
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }

0 赞同 0 条回复

lobort 普通 2022年10月27日下午9:03

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

时间、空间复杂度O(n)

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月27日下午8:54

时间复杂度为O（n），空间复杂度为O（lgn）。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        //返回当前节点的左子树和右子树的深度最大值再加1
        return Math.max(left,right)+1;
    }
}

0 赞同 0 条回复

云永久会员 2022年10月27日下午8:51

1、利用递归分别计算左右子树的深度然后+1 =树的深度
”’java
/**
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(rootnull) return 0;
int ld=TreeDepth(root.left);
int rd=TreeDepth(root.right);
return Math.max(ld,rd)+1;

}
”’
时间复杂度：

0 赞同 0 条回复

So 普通 2022年10月27日下午8:35

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

时间：O(n)，空间：(height)

0 赞同 0 条回复

波波_1936 普通 2022年10月27日下午8:21

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
    //时间复杂度O(n) n是二叉树的节点
    //空间复杂度O(height) height为二叉树的高度也就是递归占用的空间

0 赞同 0 条回复

Whatever 永久会员 2022年10月27日下午8:00

递归：计算左右子树中的最大深度，加上根节点，即为该树的最大深度，时间O(n)，空间O(n)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int maxRight = maxDepth(root.right);
        int maxLeft = maxDepth(root.left);
        int depth = 1 + (maxRight > maxLeft ? maxRight:maxLeft);
        return depth;
    }
}

0 赞同 0 条回复

just 普通 2022年10月27日下午7:55

//递归写法
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
return 1+max(maxDepth(root->left),maxDepth(root->right));

};

0 赞同 0 条回复

【二叉树专题】剑指 Offer 55 – I. 二叉树的深度

共以下 61 个回答

# 回答此问题取消回复

【二叉树专题】剑指 Offer 55 – I. 二叉树的深度

共以下 61 个回答

# 回答此问题 取消回复

# 回答此问题取消回复