513. 找树左下角的值 - 力扣（LeetCode）
image.png
两种方法，层序遍历和递归
# 递归，没有中，只有左右
# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
self.maxdepth = float('-inf')
self.result = None
self.find_bleft(root, 0)
return self.result
def find_bleft(self, cur, depth):
if cur.left == None and cur.right == None:
if depth > self.maxdepth:
self.maxdepth = depth
self.result = cur.val
return self.result
if cur.left:
depth += 1
self.find_bleft(cur.left, depth)
depth -= 1
if cur.right:
depth += 1
self.find_bleft(cur.right, depth)
depth -= 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
from collections import deque
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
if not root:
return
result = None
que = deque()
que.append(root)
while que:
n = len(que)
for i in range(n):
cur = que.popleft()
if i == 0:
result = cur.val
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return result
112. 路径总和 - 力扣（LeetCode）
image.png
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
return self.traversal(root,targetSum-root.val)
def traversal(self, cur, targetSum):
if cur.left == None and cur.right == None and targetSum == 0:
return True
if cur.left == None and cur.right == None and targetSum != 0:
return False
if cur.left:
targetSum -= cur.left.val
if self.traversal(cur.left, targetSum):
return True
targetSum += cur.left.val
if cur.right:
targetSum -= cur.right.val
if self.traversal(cur.right, targetSum):
return True
targetSum += cur.right.val
return False
106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
image.png
- 注意套路
# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
# 1、排除特殊情况
if not postorder:
return None
# 2、同一个后序遍历区间的最后一个元素是当前二叉树的root
root_val = postorder[-1]
root = TreeNode(root_val)
# 3、找中序切割点：之前root的中序index
sep_idx = inorder.index(root_val)
# 4、切割inorder数组，得到其左右半边
inorder_left = inorder[:sep_idx]
inorder_right = inorder[sep_idx + 1:]
# 5、切割postorder，
# 注意 中序的左右区间大小一定是和后序左右区间大小一样的
postorder_left = postorder[:len(inorder_left)]
postorder_right = postorder[len(inorder_left) : len(postorder) - 1]
# 6、递归
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
# 7、返回结果
return root
