leetcode 104. Maximum Depth of Binary Tree
LeetCode of Tree Binary maximum depth 104
2023-09-14 09:11:53 时间
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
For example:
Given binary tree [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
return its depth = 3.
解法1:
# 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 not root: return 0 return max(self.maxDepth(root.left)+1, self.maxDepth(root.right)+1)
解法2: BFS
# 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 not root: return 0 q = [root] ans = 0 while q: ans += 1 q = [y for x in q for y in (x.left, x.right) if y] return ans
DFS的迭代解法:在迭代tree node的过程中,使用另外一个stack追踪每一个node的高度。
# 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 not root: return 0 nodes = [root] heights = [1] ans = 0 while nodes: n = nodes.pop() h = heights.pop() ans = max(ans, h) if n.right: nodes.append(n.right) heights.append(h+1) if n.left: nodes.append(n.left) heights.append(h+1) return ans
相关文章
- leetcode 之Median of Two Sorted Arrays(五)
- Java实现 LeetCode 732 我的日程安排表 III(暴力 || 二叉树)
- Java实现 LeetCode 554 砖墙(缝隙可以放在数组?)
- Java实现 LeetCode 466 统计重复个数
- Java实现 LeetCode 432 全 O(1) 的数据结构
- Java实现 LeetCode 374 猜数字大小 II
- Java实现LeetCode 111. Minimum Depth of Binary Tree
- Java实现LeetCode 111. Minimum Depth of Binary Tree
- LeetCode(21):合并两个有序链表
- LeetCode:104_Maximum Depth of Binary Tree | 二叉树的最大深度 | Easy
- [LeetCode] Game of Life
- [LeetCode] Serialize and Deserialize Binary Tree
- LeetCode - 593 有效的正方形
- [LeetCode]Median of Two Sorted Arrays 二分查找两个有序数组的第k数(中位数)
- [LeetCode] 231. Power of Two ☆(是否2 的幂)
- [LeetCode] 191. Number of 1 Bits ☆(位 1 的个数)
- LeetCode 235: Lowest Common Ancestor of a Binary Search Tree
- LeetCode:Length of Last Word
- leetcode 559. Maximum Depth of N-ary Tree
- leetcode 345. Reverse Vowels of a String
- leetcode 235. Lowest Common Ancestor of a Binary Search Tree
- leetcode 326. Power of Three
- leetcode 747. Largest Number At Least Twice of Others
- leetcode 350. Intersection of Two Arrays II
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色