# 二刷力扣--二叉树(2)

### 226.翻转二叉树

1. 确定函数参数和返回值
函数参数为当前节点cur。无返回值。
def dd(cur):

1. 确定终止条件。当前节点为空则终止。
if not cur:
return
1. 单层逻辑
反转当前节点的左右，然后递归调用cur.left, cur.right
   def dd(cur):
if not cur:
return
cur.left, cur.right = cur.right, cur.left
dd(cur.left)
dd(cur.right)


class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dd(cur):
if not cur:
return
cur.left, cur.right = cur.right, cur.left
dd(cur.left)
dd(cur.right)
dd(root)
return root


### 101.对称二叉树

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
def symmetric_list(lst):
length = len(lst)
i = 0
j = length-1
while i < j:
if lst[i] != lst[j]:
return False
i += 1
j -= 1
return True
res = []
if not root:
return res
queue = deque()
queue.append(root)
while len(queue) > 0:
next_list = []
length = len(queue)
for i in range(length):
node = queue.popleft()
if node.left:
queue.append(node.left)
next_list.append(node.left.val)
else:
next_list.append(-9999)

if node.right:
queue.append(node.right)
next_list.append(node.right.val)
else:
next_list.append(-9999)

if not symmetric_list(next_list):
return False

return True


1. 函数参数和返回值。
参数是左子节点和右子节点。返回值是 bool值，表示是否当前节点是否轴对称。
def compare(left, right):
1. 终止条件。
左右节点全为空或某个为空时，则可以判断出当前节点的左右是否是对称的了。
if not left and not right:
return True
elif not left or not right:
return False

1. 单层逻辑
return    left.val == right.val and \
compare(left.left, right.right) and compare(left.right, right.left)


### 104.二叉树的最大深度

class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if not root:
return res
queue = deque()
queue.append(root)
while len(queue) > 0:
sub_list = []
length = len(queue) # 注意
for i in range(length):
node = queue.popleft()
sub_list.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(sub_list)
return res
def maxDepth(self, root: Optional[TreeNode]) -> int:
res = self.levelOrder(root)

return len(res)


1. 函数参数和返回值。
参数为当前节点node。返回值为int值，表示节点的深度。
2. 终止条件
节点为空时，返回0.
3. 单层逻辑
max(左节点深度,右节点深度) +1
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
def depth(node):
if not node:
return 0
leftDepth = depth(node.left)
rightDepth = depth(node.right)
return max(leftDepth, rightDepth)+1

return depth(root)

• 二叉树节点的深度：指从节点到该节点最长简单路径边的条数。
• 二叉树节点的高度：指从该节点叶子节点最长简单路径边的条数。
本题可以使用前序遍历（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度
• 而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

### 111.二叉树的最小深度

class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue  = deque()
queue.append(root)
depth = 0
while queue:
depth += 1
length = len(queue)
for i in range(length):
node = queue.popleft()
if all([not node.left, not node.right]):
return depth
for nextnode in [node.left, node.right]:
if nextnode:
queue.append(nextnode)

return depth


1. 函数参数和返回值。
参数为当前节点node。返回值为int值，表示节点的深度。
2. 终止条件
节点为空时，返回0.
3. 单层逻辑
1. 如果只有右子树，返回 1+rightDepth
如果只有左子树，返回 1+leftDepth
否则，返回 min(左节点深度,右节点深度) +1
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
def getDepth(node: Optional[TreeNode]) -> int:
if  not node :
return 0
leftDepth = getDepth(node.left)
rightDepth = getDepth(node.right)
if not node.left and node.right :
return 1+ rightDepth
if not node.right and node.left:
return 1+ leftDepth

return  1 + min(leftDepth, rightDepth)

return getDepth(root)


### 222.完全二叉树的节点个数

1. 函数参数和返回值。
参数是当前节点。返回值是当前节点为根节点的树的节点个数。
2. 终止条件
如果节点为None，返回0。
3. 单层逻辑
判断当前节点是不是满二叉树，是满二叉树则直接用公式2^树深度 - 1 返回节点数。否则递归处理左右子树，返回左子树节点数 + 右子树节点数 + 1。
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
# 判断当前节点是不是满二叉树
leftHeight, rightHeight = 0, 0
left, right = root.left, root.right
while left:
left = left.left
leftHeight += 1
while right:
right = right.right
rightHeight += 1
# 是满二叉树，则用公式计算
if leftHeight == rightHeight:
return (2 << leftHeight) -1
# 否则递归处理left, right
return self.countNodes(root.left) + self.countNodes(root.right) + 1


### 110.平衡二叉树

• 二叉树节点的深度：指从节点到该节点最长简单路径边的条数。
• 二叉树节点的高度：指从该节点叶子节点最长简单路径边的条数。

LeetCode上的不是按照路径数，而是按照节点数计算。

1. 函数参数和返回值
参数为当前节点，返回值为节点的高度。返回值为-1时表示不是平衡二叉树。
2. 终止条件
节点为None，返回0。
3. 单层逻辑
1. 求左子树高度，如果为-1，则已经不平衡了，返回-1.
求右子树高度，如果为-1，则已经不平衡了，返回-1.
如果左右子树高度差>1，不平衡，返回-1.
否则返回当前节点的高度，1 + max(leftDepth, rightDepth)
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def getHeight(node):
if not node:
return 0
leftDepth = getHeight(node.left)
if leftDepth == -1: return -1
rightDepth = getHeight(node.right)
if rightDepth == -1: return -1

if abs(leftDepth - rightDepth) > 1:
return -1
else:
return  1 + max(leftDepth, rightDepth)

return not getHeight(root) == -1


### 257.二叉树的所有路径

1. 参数和返回值
参数是当前节点、路径、（存放结果的数组）。返回值无。
2. 终止条件
到达叶子节点。
3. 单层逻辑
添加当前节点，递归（+回溯）遍历左子树和右子树。
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def traversal(cur, path, result):
path.append(cur.val)
# 终止条件：到达叶子节点了
if not any([cur.left, cur.right]):
sPath = ""
for n in path:
sPath += str(n)
sPath += "->"
sPath = sPath[:-2]
result.append(sPath)
return
# 左子树
if cur.left:
traversal(cur.left, path, result)
path.pop() # 回溯
# 右子树
if cur.right:
traversal(cur.right, path, result)
path.pop()

result = []
path = []
if not root:
return result
traversal(root, path, result)
return result


### 404.左叶子之和

1. 函数参数和返回值
参数是当前节点，返回值是当前节点的左叶子之和。
2. 终止条件
当前节点为None，返回0.
3. 单层逻辑
如果当前节点是左叶子，则要加入当前节点的值。然后加上左子树的左叶子和，右子树的左叶子和。
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
def getLeft(node):
if not node:
return 0
leftValue = getLeft(node.left)
rightValue = getLeft(node.right)
midValue = 0
# 左叶子：
# 它是父节点的左节点，同时它是叶子节点
if node.left and node.left.left == None and node.left.right ==None:
midValue =  node.left.val
return midValue + leftValue + rightValue

return getLeft(root)


### 513.找树左下角的值

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if not root:
return res
queue  = deque()
queue.append(root)
while queue:
sub_list  = []
length = len(queue)
for i in range(length):
node = queue.popleft()
sub_list.append(node.val)
for nextnode in [node.left, node.right]:
if nextnode:
queue.append(nextnode)

res.append(sub_list)
return res
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
return self.levelOrder(root)[-1][0]


1. 函数参数和返回值。
参数是当前节点和当前层数。
2. 终止条件
到达叶子节点。
3. 单层逻辑
递归处理左子树和右子树，深度+1.
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
maxDepth = -11111 # 最大深度
maxLeftValue = 0 # 最深层 最左的节点值
def traversal(root, depth):
nonlocal maxDepth, maxLeftValue
# 终止条件： 到达叶子
if not root.left and not root.right:
# 深度是最深的，更新答案
if depth > maxDepth:
maxDepth = depth
maxLeftValue = root.val
return
# 递归处理左右
if root.left:
traversal(root.left, depth+1) # 隐藏回溯
if root.right:
traversal(root.right, depth+1)
return

traversal(root,0)
return maxLeftValue


### 112.路径总和

1. 函数参数和返回值
参数：当前节点root，目标和targetSum。
返回值：bool值，表示是否满足题目要求。
2. 终止条件：
当前节点为None，返回False
3. 单层逻辑：
如果是叶子节点，判断当前值和目标值是否相等。
否则对左、右子数递归判断。
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return root.val == targetSum
return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)


|
13天前
|

12 3
|
1月前
|

18 3
|
1月前
|

10 1
|
1月前

14 1
|
1月前
|

11 1
|
1月前
|

17 1
|
1月前
|
Java Python

16 1
|
1月前
|
C++ Python

15 1
|
1月前
|

21 2
|
1月前
|

LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
14 0