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

小火普通 2023年10月3日下午11:31

递归
时间复杂度：o(n)
空间复杂度：o(n)

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

0 赞同 0 条回复

QQiing 普通 2023年9月14日下午4:19

/**
* 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;
}
return max(maxDepth(root->right), maxDepth(root->left)) + 1;
}
private:
int depth = 0;
};
时间复杂度：O(n)，空间复杂度：O(n)

0 赞同 0 条回复

谁仁普通 2023年9月7日下午3:56

struct TreeNode{
int val;
TreeNode * left;
TreeNode * right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};

int maxDepth(TreeNode* dept)
{
if(dept NULL)
{
return 0;
}
int leftDepth = maxDepth(dept->left);//左深度
int rightDepth = maxDepth(dept->right);//右深度

return max(leftDepth,rightDepth)+1;//返回遍历深度树

}//时间复杂度O（n），空间复杂度O（n）

0 赞同 0 条回复

黎明之前普通 2023年9月3日上午9:18

if(rootnull)
return 0;
int left = maxDepth(root->left);//先左遍历
int right = maxDepth(root->right);再右遍历
return max(left,right)+1;//比较左叉树和右叉树的中的大的加一为整个的

0 赞同 0 条回复

Marc 普通 2023年8月31日上午12:40

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

时间 On 空间On

0 赞同 0 条回复

羊毛同学普通 2023年8月30日上午11:19

打卡

/**
 * 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) {//作用：求以root指向的节点为根节点的二叉树的深度
    //结束条件
    if(root == NULL) return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    //函数等价关系式
    int lh = maxDepth(root->left);
    int rh = maxDepth(root->right);
    return lh >= rh ? lh+1 : rh+1;

    }

};

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月27日下午7:38

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

                   int dep1=0, dep2=0;
             if(root == null){
                return 0;
              }
              else{
                 dep1 = maxDepth(root->right);
                 dep2 = maxDepth(root->left);
                 if(dep1>dep2)
                      return dep1+1;
                 else
                     return dep2+1;
              }

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

0 赞同 0 条回复

Miracle· 普通 2023年8月26日下午10:47

/**
* 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:
// 深度优先遍历,时间复杂度o(n), 空间复杂度o(logn)
// int maxDepth(TreeNode root) {
// if (root nullptr) return 0;
// return max(maxDepth(root->left), maxDepth(root->right)) + 1;
// }

// 广度优先遍历,时间复杂度o(n), 空间复杂度o(n)
int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int ans = 0;
    while(!q.empty()) {
        int sz = q.size();
        while (sz > 0) {
            TreeNode *node = q.front();
            q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
            sz -= 1;
        }
        ans ++;
    }
    return ans;
}

};

0 赞同 0 条回复

sc_Yang 普通 2023年8月24日上午8:15

设n为节点个数
空间复杂度o(logn),时间复杂度o(n)

/**
 * 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) {
        int depth = 0;
        if(root == NULL){
            return 0;
        }
        int depthL = maxDepth(root->left) + 1;
        int depthR = maxDepth(root->right) + 1;
        depthL>depthR ? depth = depthL : depth = depthR;
        return depth;
    }
};

0 赞同 0 条回复

sincere 普通 2023年8月21日下午11:12

思路：递归计算左右深度
复杂度：时间复杂度O(n)，空间复杂度O(n)

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 条回复

💮黧大王.exe 普通 2023年8月21日下午6:58

时间复杂度：O(n)
空间复杂度：O(height)
class Solution {
public:
int maxDepth(TreeNode* root) {
if(rootNULL) return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};

0 赞同 0 条回复

Sheng 永久会员 2023年8月20日下午9:35

直接写函数
”’java
if(root null) {
return 0;
}

    int depLeft = maxDepth(root.left);
    int depRight = maxDepth(root.right);

    return ((depLeft>depRight)? depLeft : depRight) + 1;

0 赞同 0 条回复

辰北、普通 2023年8月20日下午5:25

//root空0；左右最大+1；
int maxDepth(struct TreeNode* root){
if(root NULL){
return 0;
}
return fmax(maxDepth(root->left),maxDepth(root->right))+1;

}

0 赞同 0 条回复

天亮说晚安普通 2023年8月20日上午11:24

打卡

class Solution {

    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int lhight = maxDepth(root.left) + 1;
        int rhight = maxDepth(root.right) + 1;
        return lhight>rhight ? lhight : rhight;
    }
}

0 赞同 0 条回复

木木普通 2023年8月19日下午11:06

時間複雜度 O(n) n為二叉樹中節點數量空間複雜度 O(height) height為二叉樹深度


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

0 赞同 0 条回复

Puff 普通 2023年8月19日上午11:56

Python 递归
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0

    L = self.maxDepth(root.left)
    R = self.maxDepth(root.right)

    return max(L,R) + 1

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月19日上午10:48

自己写对的递归！开心！

“`python
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0

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

    return depth

“`python

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月18日下午10:38

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;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(9);
        TreeNode node3 = new TreeNode(20);
        TreeNode node4 = new TreeNode(15);
        TreeNode node5 = new TreeNode(7);

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

        Solution sol = new Solution();
        int i = sol.maxDepth(node1);
        System.out.println(i);
    }
}

取左子树和右子树最大深度，递归。

0 赞同 0 条回复

小肸永久会员 2023年8月18日下午12:28

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        //以当前节点为根节点，取左右子节点中深度最大的值 + 1，返回当前节点的最大深度
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月17日下午10:47

1、队列实现层序遍历

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

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月17日下午10:34

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

0 赞同 0 条回复

帝心引力永久会员 2023年8月17日下午9:54

int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        if(root->left == nullptr && root->right == nullptr) return 1;

        int ldepth = maxDepth(root->left);
        int rdepth = maxDepth(root->right);

        return max(ldepth, rdepth) + 1;
    }
时间o(n)，空间o(h).
n为节点个数，h为高度

1 赞同 0 条回复

晓宇普通 2023年8月17日下午9:36

class Solution(object):
    def __init__(self):
        self.depth = 0
        self.maxdepth = 0
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.traverse(root)
        return self.maxdepth

    def traverse(self,root):
        if not root:
            return None
        self.depth +=1
        self.traverse(root.left)
        self.traverse(root.right)
        if self.maxdepth <= self.depth:
            self.maxdepth = self.depth
        self.depth -= 1

Consider the self.parameter and enter in/out 在

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月17日下午8:11

递归算法

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

0 赞同 0 条回复

JustRtn 普通 2023年8月17日下午4:16

深度优先搜索

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

0 赞同 0 条回复

行动派小彩笔普通 2023年8月17日下午4:16

// 时间O(n),空间O(log n)

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

0 赞同 0 条回复

逸兴遄飞普通 2023年8月17日下午4:04

深度优先搜索
+ 时间复杂度O(N), N表示二叉树总节点数；
+ 空间复杂度O(Height)， Height表示二叉树的高度。

class Solution {
    public int maxDepth(TreeNode root) {
        // 先排除空树
        if(root == null){
            return 0;
        }
        // 递归，直接返回最后的最大值并加上根节点
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
}

0 赞同 0 条回复

Joel 普通 2023年8月17日下午3:51

递归

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

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

0 赞同 0 条回复

c 普通 2023年8月17日下午1:36

递归

/**
 * 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;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

0 赞同 0 条回复

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

共以下 29 个回答

# 回答此问题取消回复

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

共以下 29 个回答

# 回答此问题 取消回复

# 回答此问题取消回复