二叉树总结
104. 二叉树的最大深度
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
left := maxDepth(root.Left)
right := maxDepth(root.Right)
if left < right {
return right + 1
}
return left + 1
}
110. 平衡二叉树
class Solution:
res = True
def isBalanced(self, root: TreeNode) -> bool:
def tree_depth(root):
if not root: return 0
if not self.res: return 0 # 剪枝操作
left_depth = tree_depth(root.left) # 左子树深度
right_depth = tree_depth(root.right) # 右子树深度
if abs(left_depth - right_depth) > 1: # 验证是否是平滑二叉树
self.res = False
return max(left_depth, right_depth) + 1
tree_depth(root)
return self.res
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func abs(a int) int {
if a < 0 {
return -1 * a
}
return a
}
func tree_depth(root *TreeNode) int {
if root == nil {
return 0
}
if flag == false {
return -1
}
left := tree_depth(root.Left)
right := tree_depth(root.Right)
if abs(left - right) > 1 {
flag = false
return - 1
}
return max(left, right) + 1
}
var flag bool
func isBalanced(root *TreeNode) bool {
flag = true
tree_depth(root)
return flag
}
543. 二叉树的直径
class Solution:
ans = 0
def diameterOfBinaryTree(self, root: TreeNode) -> int:
def maxHeight(root):
if not root: return 0
leftMaxHeight = maxHeight(root.left)
rightMaxHeight = maxHeight(root.right)
self.ans = max(self.ans, leftMaxHeight + rightMaxHeight)
return max(leftMaxHeight, rightMaxHeight) + 1
maxHeight(root)
return self.ans
func max(a, b int) int {
if a > b {
return a
}
return b
}
func maxHeight(root *TreeNode) int {
if root == nil {
return 0
}
leftMaxHeight := maxHeight(root.Left)
rightMaxHeight := maxHeight(root.Right)
ans = max(ans, leftMaxHeight + rightMaxHeight)
return max(leftMaxHeight, rightMaxHeight) + 1
}
var ans int
func diameterOfBinaryTree(root *TreeNode) int {
if root == nil {
return 0
}
ans = 0
maxHeight(root)
return ans
}
437. 路径总和 III
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
def pathSumStartWithRoot(root, sum):
if not root: return 0
count = int(root.val == sum) # 找到结果加1
count += pathSumStartWithRoot(root.left, sum - root.val)
count += pathSumStartWithRoot(root.right, sum - root.val)
return count
if not root: return 0
# 1. 从 root 开始
# 2. 从 root.left 开始
# 3. 从 root.right 开始
ans = pathSumStartWithRoot(root, sum) + \
self.pathSum(root.left, sum) + \
self.pathSum(root.right, sum)
return ans
func pathSumStartWithRoot(root *TreeNode, sum int) int {
if root == nil {
return 0
}
count := 0
if root.Val == sum {
count += 1
}
return count + pathSumStartWithRoot(root.Left, sum - root.Val) +
pathSumStartWithRoot(root.Right, sum - root.Val)
}
func pathSum(root *TreeNode, sum int) int {
if root == nil {
return 0
}
return pathSumStartWithRoot(root, sum) +
pathSum(root.Left, sum) +
pathSum(root.Right, sum)
}
101. 对称二叉树
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def isSame(A, B):
if not A and not B: return True
if not A or not B: return False
if A.val != B.val: return False
return isSame(A.left, B.right) and isSame(A.right, B.left)
if not root: return True
return isSame(root.left, root.right)
func isSame(a *TreeNode, b *TreeNode) bool {
if a == nil && b == nil {
return true
}
if a == nil || b == nil {
return false
}
if a.Val != b.Val {
return false
}
return isSame(a.Left, b.Right) && isSame(a.Right, b.Left)
}
func isSymmetric(root *TreeNode) bool {
if root == nil || (root.Left == nil && root.Right == nil) {
return true
}
return isSame(root.Left, root.Right) && isSame(root.Right, root.Left)
}
1110. 删点成林
本题当花了很多时间，可以想想思路
class Solution:
def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
def dfs(root):
if not root: return root
root.left = dfs(root.left)
root.right = dfs(root.right)
if root.val in to_delete:
if root.left:
ans.append(root.left)
if root.right:
ans.append(root.right)
return None
return root
ans = []
if dfs(root):
ans.append(root)
return ans
func helper(root *TreeNode, to_delete []int ) *TreeNode {
if root == nil {
return root
}
root.Left = helper(root.Left, to_delete)
root.Right = helper(root.Right, to_delete)
if contains(to_delete, root.Val) { // 删除节点 root
if root.Left != nil {
ans = append(ans, root.Left)
}
if root.Right != nil {
ans = append(ans, root.Right)
}
return nil
}
return root
}
func contains(data []int, value int) bool{
for _, v := range data {
if value == v {
return true
}
}
return false
}
var ans []*TreeNode
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
ans = make([]*TreeNode, 0)
if helper(root, to_delete) != nil { // 没有删除的话，加入 root
ans = append(ans, root)
}
return ans
}
124. 二叉树中的最大路径和
import math
class Solution:
res = -math.inf
def maxPathSum(self, root: TreeNode) -> int:
def dfs(root):
if not root: return 0
left_value = max(0, dfs(root.left))
right_value = max(0, dfs(root.right))
value = root.val + left_value + right_value
self.res = max(self.res, value)
return root.val + max(left_value, right_value) # 遇到岔路口，必须选择一个走
dfs(root)
return self.res
102. 二叉树的层序遍历
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
queue, res = collections.deque(), []
queue.append(root)
while queue:
res_temp = []
for _ in range(len(queue)):
temp = queue.popleft()
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
res_temp.append(temp.val)
res.append(res_temp)
return res
107. 二叉树的层次遍历 II
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root: return []
queue, res = collections.deque(), collections.deque()
queue.append(root)
while queue:
level_tmp = []
for _ in range(len(queue)):
temp = queue.popleft()
level_tmp.append(temp.val)
if temp.left: queue.append(temp.left)
if temp.right: queue.append(temp.right)
res.appendleft(level_tmp)
return list(res)
103. 二叉树的锯齿形层次遍历
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
queue, res = collections.deque(), []
queue.append(root)
level = 0
while queue:
level += 1
_res = collections.deque()
for _ in range(len(queue)):
temp = queue.popleft()
if level % 2 == 0:
_res.appendleft(temp.val)
else:
_res.append(temp.val)
if temp.left: queue.append(temp.left)
if temp.right: queue.append(temp.right)
res.append(list(_res))
return res