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

越努力越幸运普通 2024年12月19日下午11:51

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

0 赞同 0 条回复

LovLe 普通 2024年12月19日上午8:15

递归

传递下去，值归回来

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0   # 一个节点null，深度为0 # 最底层返回的数值
        if root.left and root.right:    # 两个子树，深度为两者的最大深度+1
            return max(self.maxDepth(root.left),self.maxDepth(root.right))+1  #向下递推公式  
        return self.maxDepth(root.left)+1 if root.left else self.maxDepth(root.right)+1 #只有一个子树，存在的子树深度+1

向下递推公式，直到返回底层值，又向上返回赋予值。

直接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left)+1,self.maxDepth(root.right)+1)  #递推公式

层序遍历

让每次全部pop一层的节点后，layer才加1。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        queue=[root]
        layer=0
        while queue:
            length=len(queue)   #增加了这个
            for _ in range(length):
                cur=queue.pop(0)
                if cur.left: queue.append(cur.left)
                if cur.right: queue.append(cur.right)
            layer+=1    # 层数+1
        return layer

0 赞同 0 条回复

yelinliner 普通 2024年12月16日下午3:53

递归三步法：

函数的定义：f(root) ：计算当前节点的深度

找关系式：f(root)=max(f(left),f(right))+1

初始值：root=null return 0

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

0 赞同 0 条回复

mpweixin用户普通 2024年12月14日下午3:35

层序遍历

class Solution {
public:
    int calculateDepth(TreeNode* root) {
        if(root == NULL) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int result = 0;
        int num = 1;
        while(num != 0){
            TreeNode* temp = q.front();
            q.pop();
            if(temp->left) q.push(temp->left);
            if(temp->right) q.push(temp->right);
            num--;
            if(num == 0){
                num = q.size();
                result++;
            }
        }
        return result;
    }
};

递归
1.传入根节点，传出当前根节点树的深度
2.出口返回深度int
3.递归函数：当前树深=左右子树最大深度+1
时间O(N), 空间O(N)

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

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

0 赞同 0 条回复

晓宇普通 2024年12月5日下午3:29

class Solution {
public:
    // 思路：分别求取左子树和右子树的深度，取最大值为整颗数的深度
    int calculateDepth(TreeNode* root) {
        if(!root) return 0;
        int l = calculateDepth(root->left);
        int r = calculateDepth(root->right);
        return max(l,r) + 1;
    }

};
// 时间复杂度:o(n); 空间复杂度:o(log n)

0 赞同 0 条回复

岱永久会员 2024年12月5日下午1:36

递归

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

    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年12月5日上午12:24

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def calculateDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.calculateDepth(root.left), self.calculateDepth(root.right)) + 1

0 赞同 0 条回复

🌟 普通 2024年12月3日下午7:45

直接递归

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

0 赞同 0 条回复

Pendulumpal 普通 2024年12月2日下午3:26

直接进行简单的遍历

    int depth;
    public void dfs(TreeNode root, int cnt){
        if(root==null)return;
        depth=Math.max(depth,cnt);
        dfs(root.left,cnt+1);
        dfs(root.right,cnt+1);
    }

    public int calculateDepth(TreeNode root) {
        if(root==null)return 0;
        depth=0;
        dfs(root,1);
        return depth;
    }

0 赞同 0 条回复

陆狗陆狗普通 2024年12月1日下午2:46

题解

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

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午5:42

/**
方法一：递归
树的深度=max(左子树最大深度，右子树最大深度) + 1
时间复杂度O(N)
 */
class Solution {
    public int calculateDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        return Math.max(calculateDepth(root.left), calculateDepth(root.right)) + 1;

    }
}

0 赞同 0 条回复

Tom Yuan 普通 2024年11月29日下午2:57

递归走左边和右边，然后结果取max 并+1来保证计数器自增。

class Solution:
    def calculateDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        left = self.calculateDepth(root.left)
        right = self.calculateDepth(root.right)

        # remember to +1 so that the value can increase.
        return max(left, right) + 1

time O(n) space O(n) 递归过程中会有n个结果

0 赞同 0 条回复

Renasc 普通 2024年11月28日下午7:43

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

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

        int left = calculateDepth(root.left);
        int right = calculateDepth(root.right);

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

0 赞同 0 条回复

Jerry 普通 2024年11月28日上午11:04

class Solution {
public:
    int calculateDepth(TreeNode* root) {
        if(!root) return 0;

        return max(calculateDepth(root->left), calculateDepth(root->right))+1;

    }
};

时间o(n)
空间o(n)

0 赞同 0 条回复

🍊 普通 2024年11月27日下午10:56

“`java
/**
* 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 calculateDepth(TreeNode root) {
if(root == null) return 0;
return 1 + Math.max(calculateDepth(root.left), calculateDepth(root.right));
}
}
递归即可

0 赞同 0 条回复

黑键〰普通 2024年11月27日下午9:39

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var calculateDepth = function(root) {
    if(!root) return 0
    // 回溯
    // return Math.max(calculateDepth(root.left), calculateDepth(root.right))+1
    // bfs
    let q = [root]
    let depth = 0
    while(q.length) {
        // 需要记录每层队列的长度
        let len = q.length
        while(len > 0) {
            let cur = q.shift()
            if(cur.left !== null) {
                q.push(cur.left)
            }
            if(cur.right !== null) {
                q.push(cur.right)
            }
            len--
        }
        depth++
    }
    return depth
};

思路：一种可以直接递归，终止条件是最后节点为null时返回0；
另一种是层序遍历BFS，但是需要记录每一层节点的数量，循环完一层的queue之后深度才加一

0 赞同 0 条回复

jaron 普通 2024年11月27日下午9:10

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

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

0 赞同 0 条回复

休一普通 2024年11月27日下午8:47

1.代码

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

2.复杂度分析

a.时间复杂度o(n)；
b.空间复杂度o(n)，递归过程会产生内存。

0 赞同 0 条回复

Kisara 普通 2024年11月27日下午7:58

/**
 * 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 calculateDepth(TreeNode root) {
        if(root==null) return 0;

        int leftDepth=calculateDepth(root.left)+1;
        int rightDepth=calculateDepth(root.right)+1;

        return Math.max(leftDepth,rightDepth);
    }
}

时间O（n）空间O（n）

0 赞同 0 条回复

无言永久会员 2024年11月27日下午5:24

class Solution {
public:
    int calculateDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        return max(calculateDepth(root->left), calculateDepth(root->right)) + 1;
    }
};
递归 当前高度 = max(左子树高度, 左子树高度) + 1
时间复杂度 O(N)
空间复杂度 O(N)

0 赞同 0 条回复

秋山丽奈普通 2024年11月27日下午4:51

思路：递归解决。当前高度 = Math.max(子树高度) + 1

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

    int getDepth(TreeNode node){
        if(node == null){
            return 0;
        }

        int leftDepth = getDepth(node.left);
        int rightDepth = getDepth(node.right);

        return Math.max(leftDepth, rightDepth) + 1;
    }
}

0 赞同 0 条回复

月下足迹普通 2024年11月27日下午3:37

/ 时间复杂度为O(N),空间复杂度最坏为O(N)

/**
* 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 calculateDepth(TreeNode root) {
if(root null) {
return 0;
}

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

    return Math.max(leftDepth, rightDepth) + 1;
}

}

0 赞同 0 条回复

迢迢星野普通 2024年11月27日上午10:00

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

    private 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)，每个节点被访问一次
空间复杂度：O(h)，递归调用栈的深度取决于二叉树的高度。

0 赞同 0 条回复

lQl 永久会员 2024年11月27日上午9:40

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

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

0 赞同 0 条回复

苯庸普通 2024年11月27日上午9:27

class Solution {
public int calculateDepth(TreeNode root) {
if(root null){
return 0;
}
return Math.max(calculateDepth(root.left), calculateDepth(root.right)) + 1;
}
}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

youngsir 普通 2024年11月27日上午9:20

打卡，递归

/**
 * 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 calculateDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        int leftdepth = calculateDepth(root->left);
        int rightdepth = calculateDepth(root->right);
        int depth = 1 + max(leftdepth,rightdepth);
        return depth;
    }
};

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

0 赞同 0 条回复

Xiang. 永久会员 2024年11月27日上午9:08

思路：通过递归使用后序遍历，获取左子树、右子树的深度，将其最大值返回给根节点即可
/**
 * 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 calculateDepth(TreeNode root) {
        if(root==null) return 0;
        return Math.max(calculateDepth(root.left)+1,calculateDepth(root.right)+1);
    }
}
时间复杂度o（n）
空间复杂度o（n）

0 赞同 0 条回复

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

共以下 27 个回答

递归

直接

层序遍历

1.代码

2.复杂度分析

# 回答此问题取消回复

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

共以下 27 个回答

递归

直接

层序遍历

1.代码

2.复杂度分析

# 回答此问题 取消回复

# 回答此问题取消回复