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

hi 普通 2023年8月4日下午9:58

递归：
1. 明确递归函数作用
2. 找递归函数退出边界条件
3. 找函数关系缩小函数范围

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

0 赞同 0 条回复

今天没时间刷题普通 2023年7月30日下午12:23

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

0 赞同 0 条回复

wowo 普通 2023年7月25日上午4:26

迭代，时间复杂度O(n) n是节点数，空间复杂度O(height)

# 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 not root:
            return 0

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

0 赞同 0 条回复

finalrgy 普通 2023年7月22日下午3:44

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)
    if leftDepth < rightDepth {
        leftDepth = rightDepth
    }
    return leftDepth + 1
}

递归遍历左子树和右子树
时间O(N) 空间O(N)

0 赞同 0 条回复

doordie. 普通 2023年7月17日下午7:40

递归

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

0 赞同 0 条回复

朱志刚普通 2023年7月17日下午6:23

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

今天你刷题了嘛普通 2023年7月16日下午9:55

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+1,right+1);
    }
}

时间复杂度：O(N)
空间复杂度：O（1）

0 赞同 0 条回复

神经蛙普通 2023年7月16日下午12:07

/**
    时间复杂度O(n)
    空间复杂度O(1)
    递归-后序遍历二叉树
*/
class Solution {

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

        int leftLength = maxDepth(root.left);
        int rightLength = maxDepth(root.right);

        return Math.max(leftLength, rightLength) + 1;
    }

}

0 赞同 0 条回复

周小二普通 2023年7月15日下午10:11

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

0 赞同 0 条回复

ppopp 普通 2023年7月15日下午8:17

/**中文
* 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 nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};

0 赞同 0 条回复

Marshan 普通 2023年7月15日下午7:28

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

0 赞同 0 条回复

人生何处不青山普通 2023年7月15日下午6:02

简单题

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
    if(!root) return 0;
    return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
};

0 赞同 0 条回复

June 普通 2023年7月15日下午3:27

/**
 * 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
    }

    var lh int = maxDepth(root.Left)
    var rh int = maxDepth(root.Right)

    return int(math.Max(float64(lh),float64(rh))) + 1 //选最深的

}

0 赞同 0 条回复

Terence💧 普通 2023年7月15日下午1:21

二叉树深度

/**
 * 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 max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

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

0 赞同 0 条回复

片言莫语普通 2023年7月14日下午10:01

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

Mby 普通 2023年7月14日下午8:39

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月14日下午4:56

用队列代替递归方法

#include<queue>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};
// @lc code=start
class Solution {
public:
  int maxDepth(TreeNode *root) { 
    if(root == nullptr)
      return 0;
    queue<TreeNode *> nodes;
    int max=0,size;
    TreeNode *tmp;

    nodes.push(root);
    while(!nodes.empty()){
        size=nodes.size();
      for (int i = 0; i < size;i++){
        tmp = nodes.front();
        nodes.pop();
        if(tmp->right != nullptr){
            nodes.push(tmp->right);
        }
        if(tmp->left != nullptr){
            nodes.push(tmp->left);
        }
      }
      max++;
    }

    return max;
  }

};

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月14日下午3:46

/**
* 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) {
return 0;
}
int left = maxDepth(root->left); // 递归
int right = maxDepth(root->right); // 递归

    return max(left, right) + 1;
}

};

0 赞同 0 条回复

枫梓。普通 2023年7月14日下午1:30

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        queue<TreeNode*> q;
        q.push(root);
        int height = 0;
        while(!q.empty()){
            int size = q.size();
            for(int i = 0; i < size; i++) {
                auto u = q.front(); q.pop();
                if(u->left)
                    q.push(u->left);
                if(u->right)
                    q.push(u->right);
            }
            height++;
        }
        return height;
    }
};

层序遍历了

0 赞同 0 条回复

#00456B 普通 2023年7月13日下午10:35

两种方法，一种是用回溯的方法，一种是遍历二叉树

/**
 * 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;
    //     }
    //     int leftMax = maxDepth(root->left);
    //     int rightMax = maxDepth(root->right);
    //     return 1+max(leftMax,rightMax);
    // }
    int depth = 0;
    int ans = 0;
    int maxDepth(TreeNode* root) {
        traverse(root);
        return ans;
    }
    void traverse(TreeNode* root){
        if(root == NULL){
            return ;
        }
        depth++;
        ans = max(ans, depth);
        traverse(root->left);
        traverse(root->right);
        depth--;
    }
};

0 赞同 0 条回复

CaCO3 永久会员 2023年7月13日下午8:08

”’java
class Solution {
public int maxDepth(TreeNode root) {
if(root null){
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return leftDepth > rightDepth ? leftDepth+1:rightDepth+1;
}
}
”’
时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

坏掉的世界永久会员 2023年7月13日下午7:02

代码

class Solution {
public:
    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年7月13日下午6:36

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

时间复杂度：O（n）
空间复杂度：O（height） height是树的高度

0 赞同 0 条回复

NullPointerException 普通 2023年7月13日下午5:28

“`java
class Solution {
//经典递归
int max =0;
public int maxDepth(TreeNode root) {
if(root==null)
{
return 0;
}
int left =maxDepth(root.left);
int right =maxDepth(root.right);
if(left>right)
{
max=left;
}else
{
max=right;
}

    return max+1;
}

}

0 赞同 0 条回复

V2ero 普通 2023年7月13日下午3:59

深度优先

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
       if(root === null){
           return 0
       } else {
           let left = maxDepth(root.left);
           let right = maxDepth(root.right);
           return Math.max(left,right) +  1
       }
};

0 赞同 0 条回复

CKX 普通 2023年7月13日下午3:54

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    maxDepth := 0
    var traverse func(*TreeNode, int)
    traverse = func (root *TreeNode, depth int) {
        if root == nil {
            return
        }
        depth++

        //如果是叶子节点，更新最大深度
        if root.Right == nil && root.Left == nil {
            maxDepth = max(maxDepth, depth)
        }
        traverse(root.Left, depth)
        traverse(root.Right, depth)
    }

    traverse(root, 0)
    return maxDepth
}



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

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月13日下午3:29

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

0 赞同 0 条回复

momo 普通 2023年7月13日下午3:11

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

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

阿尚普通 2023年7月13日上午9:21

class Solution {
    public int maxDepth(TreeNode root) {
        return travel(root);
    }

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

        int leftDepth = travel(root.left);
        int rightDepth = travel(root.right);

        return Math.max(leftDepth, rightDepth) + 1;//返回左右子树最大高度+1
    }
}

0 赞同 0 条回复

波雅汉库克普通 2023年7月13日上午5:32

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        deque<TreeNode*> dq;
        dq.push_back(root);
        int maxDep = 0;
        while(!dq.empty()){
            maxDep++;
            int len = dq.size();
            while(len > 0){
                TreeNode* top = dq.front();
                dq.pop_front();
                if(top->left!=nullptr){
                    dq.push_back(top->left);
                }    
                if(top->right!=nullptr){
                    dq.push_back(top->right);
                }
                len--;
            }
        }
        return maxDep--;
    }
};

时间：o(n)

0 赞同 0 条回复

普通 2023年7月12日下午11:56

c++ 代码层次遍历
class Solution {
public:
queue<TreeNode> inQueue;
int maxDepth(TreeNode root)
{
if(!root) return 0;
inQueue.push(root);
int count=0;

        while(inQueue.size())
        {
            int n=inQueue.size();
            for(int i=0;i<n;i++)
            {
                TreeNode* te=inQueue.front();
                inQueue.pop();
                if(te->left!=NULL) inQueue.push(te->left);
                if(te->right!=NULL) inQueue.push(te->right);
            }
            count++;
        }
        return count;
}

};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月12日下午11:38

Day6：下面是代码

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年7月12日下午11:28

class TreeNode:
    def __init__(self, x):
        self.value = x
        self.left = None
        self.right = None


class Solution:
    def maxDepth(self, root: TreeNode):
        if root is None:
            return 0

        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)

            # 深度优先搜索
            max_height = max(left_height, right_height)
            max_depth = max_height + 1
            return max_depth

"""
时间复杂度： O(N), N为节点个数
空间复杂度：O(height), height为二叉数的高度
"""

0 赞同 0 条回复

艺普通 2023年7月12日下午10:38

“`c++
//自顶向下
class Solution {
public:
int ans=0;
void dfs(TreeNode* T,int deep)
{
if(T = =NULL)
{
ans =max(ans , deep);
return;
}
dfs(T->left,deep+1);
dfs(T->right,deep+1);
}
int maxDepth(TreeNode* root) {
dfs(root,0);
return ans;
}
};

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月12日下午8:16

代码

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

Luminous 普通 2023年7月12日下午5:28

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

时间复杂度：O(N)
空间复杂度:O(1)

0 赞同 0 条回复

ONE PIECE 普通 2023年7月12日下午5:23

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

时间复杂度：O(N);
空间复杂度：O(1);

0 赞同 0 条回复

桎梏普通 2023年7月12日下午5:10

递归求左右子树

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

0 赞同 0 条回复

AD钙奶普通 2023年7月12日下午4:28

打卡

class Solution {
    public int maxDepth(TreeNode root) {
        return getDepth(root);
    }

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

0 赞同 0 条回复

Mooby 普通 2023年7月12日下午3:50

六
/**
* 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;
}
}

0 赞同 0 条回复

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

共以下 40 个回答

递归

# 回答此问题取消回复

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

共以下 40 个回答

递归

# 回答此问题 取消回复

# 回答此问题取消回复