树的总结，前序中序后序遍历实现
三种遍历的实现方式
144. 二叉树的前序遍历
class Solution(object): def helper(self, root, res): if not root: return res.append(root.val) self.helper(root.left, res) self.helper(root.right, res) def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ res = [] if not root: return res self.helper(root, res) return res def preorderTraversal2(self, root): """ :type root: TreeNode :rtype: List[int] """ res = [] if not root: return res stack = [root] while stack: cur = stack.pop() res.append(cur.val) if cur.right: stack.append(cur.right) if cur.left: stack.append(cur.left) return res
145. 二叉树的后序遍历
递归就记住
迭代：结果数组加入的时候从头加，栈里面先存入头节点；每次栈中弹出最后一个元素，从头加入结果数组；如果有左右节点记得加入栈！
class Solution(object): def helper(self, res, root): if not root: return self.helper(res, root.left) self.helper(res, root.right) res.append(root.val) def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ res = [] if not root: return res self.helper(res, root) return res def postorderTraversal2(self, root): """ :type root: TreeNode :rtype: List[int] """ res = [] if not root: return res stack = [root] while stack: cur = stack.pop() res.insert(0, cur.val) if cur.left: stack.append(cur.left) if cur.right: stack.append(cur.right) return res
class Solution(object): def helper(self, res, root): if not root: return res self.helper(res, root.left) res.append(root.val) self.helper(res, root.right) def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ res = [] if not root: return res self.helper(res, root) return res
中序的迭代形式最常考
开始先把所有的左节点加入栈， 第一次遍历的时候cur的顺序是文本形式的1，2，3
class Solution(object): def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ res = [] if not root: return res cur = root stack = [] while cur oor stack: while cur: stack.append(cur) cur = cur.left cur = stack.pop() res.append(cur.val) cur = cur.right return res
双pre 不涉及到遍历
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if not root: return False if not root.left and not root.right: return sum == root.val return self.hasPathSum(root.left, sum-root.val) oor self.hasPathSum(root.right, sum-root.val)
Inorder的题目和解法
基本上全和BST 升序相关
class Solution: def helper(self, res, root): if not root: return self.helper(res, root.left) res.append(root.val) self.helper(res, root.right) def kthSmallest(self, root: TreeNode, k: int) -> int: res = [] self.helper(res, root) return res[k - 1]
Postorder的题目和解法
子模块 子树 从底层到上层# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.res = float('-inf')
def helper(self, root):
if not root:
return 0
left = max(0, self.helper(root.left))
right = max(0, self.helper(root.right))
self.res = max(self.res, left+right+root.val)
return max(left, right) + root.val
def maxPathSum(self, root: TreeNode) -> int:
if not root:
return 0
self.helper(root)
return self.res self.res存储的是结果， helper return的是一条路径104. 二叉树的最大深度
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
你想占我便宜我就占你便宜，谁也拿我没办法，主打一个双向奔赴