更弱智的算法学习 day12-平芜编程栈

第六章二叉树part01

理论基础

二叉树：首先是三种遍历方法

递归遍历（必须掌握）

递归算法的重点内容

1、确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2、确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3、确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

前序遍历，也即沿着左侧一路向下，直到遇到空节点，再回到上一个节点，之后遍历右节点，完成后再返回上一节点，如此往复

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: vec = [] def preorder(cur): if cur is None: return vec.append(cur.val) preorder(cur.left) preorder(cur.right) preorder(root) return vec

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: vec = [] def bfs(cur): if cur is None: return bfs(cur.left) bfs(cur.right) vec.append(cur.val) bfs(root) return vec

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: vec = [] def bfs(cur): if cur is None: return bfs(cur.left) vec.append(cur.val) bfs(cur.right) bfs(root) return vec

一次三道题，享受

迭代遍历（基础不好的录友，迭代法可以放过）

迭代遍历的思路是，使用一个栈来存放要处理的节点。首先判断根结点是否为空，如果为空则返回空列表。之后把根节点入栈，当栈中还有需要处理的元素时，首先处理栈顶的元素，把元素值保存到列表里。然后查看其右节点，如果有则入栈；再查看其左节点，如果有则入栈。（这里需要注意，前序遍历是中左右，这里栈是处理后进先出，所以入栈的顺序应该是右左）

class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if root is None: return [] vec = [] stack = [root] while stack: node = stack.pop() vec.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return vec

前序遍历是中左右，而将前序遍历左右调换顺序，就变成中右左，再对最终的数组反转，就变成左右中，也即后序遍历。

class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if root is None: return [] vec = [] stack = [root] while stack: node = stack.pop() vec.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return vec[::-1]

中序遍历思路不完全一致，其逻辑是左中右，因此我们需要遍历到左侧末端再向上查找。因此判断结束的条件需要修改，只有当前节点和栈中都空才结束：当前节点存在时，首先入栈，再找左侧节点；直到当前节点不存在时，（cur指到空的时候，就从栈里面去元素，直到栈里也没有元素，此时就停在右侧节点的尾部）处理栈里的节点并存入到列表中，再寻找右侧节点

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] vec = [] stack = [] cur = root while cur or stack: if cur: stack.append(cur) cur = cur.left else: cur = stack.pop() vec.append(cur.val) cur = cur.right return vec

统一迭代（基础不好的录友，迭代法可以放过）
这个部分暂时放过

层序遍历

代办已经很多了= =

102.二叉树的层序遍历(opens new window)

层序遍历要从每一层里获取节点值：本题使用队列手机节点数值

定义一个result列表用来储存每一层的内容。首先判定根节点是否存在。存在后将根节点入队。

判定的条件是队列非空，因为在每一层中需要保存当层的节点，因此需要定义一个size来保存队列长度，定义level逐层保存节点的数组。

用size的长度进行循环，因为只接受size个节点。对每一层的节点，先取出对头，收集对头的节点。查找对头节点的左节点和右节点，保存到队列中，完成一层的遍历后，把该层的节点保存到level数组中，由result进行扩展。

# 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]]: queue = [] result = [] if root is None: return [] queue.append(root) while queue: size = len(queue) level = [] for i in range(size): node = queue.pop(0) level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result

后续还有一些题目等待处理= - =，很疲惫了