.png?table=block&id=c7f2ac07-416c-46b2-ad08-e27bdb862087&cache=v2)
LeetCode
👨🏻💻 Github repo:
树的问题
这类问题有个大体的框架 👇：
def traverse_tree(root: Node):
// 先序遍历代码位置
traverse(root.left)
// 中序遍历代码位置
traverse(root.right)
// 后序遍历代码位置回到实际的问题中来，先序遍历和后序遍历的特点是：
- 先序遍历的第一个节点为根结点 root
- 后序遍历的最后一个节点为根节点 root
- 中序遍历中，root 节点的左边部分为 root 的左子树，root 节点的右边部分为 root 的右子树
105 & 106
根据先序遍历和中序遍历还原一棵树 or 根据中序遍历和后续遍历还原一棵树。
掌握了上面说的树的规律，基本上就有如下解题步骤：
- 边界条件
if not preorder or not inorder:
return None- 找到根结点 root
- 找到 root 在中序遍历中的索引
- 构造 root node
- 如果条件是
inorder + preorder，则先遍历左子树再遍历右子树；如果条件是inorder + postorder，则先遍历右子树再遍历左子树。
原因：
对于知道preorder的情况，preorder第二个节点是level 2中左子树的根结点，因此递归的时候注意先递归左子树； 而对于知道postorder的情况，postorder 的倒数第二个节点是level 2中右子树的根结点，因此递归的时候注意先递归右子树；
- 前序遍历和中序遍历
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None
# 这里的 pop 出第一个节点很关键，先序遍历第一个节点就是根结点
root_val = preorder.pop(0)
ind = inorder.index(root_val)
root = TreeNode(root_val)
root.left = self.buildTree(preorder, inorder[0:ind])
root.right = self.buildTree(preorder, inorder[ind+1:])
return root- 后序遍历和中序遍历
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not inorder or not postorder:
return None
root = TreeNode(postorder.pop())
ind = inorder.index(root.val)
# 这里的关键在于，先要递归生成右子树，原因：
# postorder 倒数第二个节点是 level 2 右子树的根结点，而不是左子树，因此
# 必须先生成右子树而非左子树
root.right = self.buildTree(inorder[ind+1:], postorder)
root.left = self.buildTree(inorder[:ind], postorder)
return root116
填充每一个节点的下一个右侧节点指针
还是使用递归的办法，但是会和简单的递归思维有一些改动的地方。
首先，我们最容易想到如下这种递归：
def connect(root):
if not root or not root.left: return None
root.left.next = root.right
connect(root.left)
connect(root.right)
return root但这样会有一个问题：
当两个节点拥有同一个父节点时，上面的做法是可行的。而仔细观察后我们发现，5 和 6 节点并没有连接同一个父节点，这时候，从 5 → 6 的操作就有问题了。
既然这个题递归时使用一个节点不行，那么我们换一种思维，使用两个节点来连接，是不是就可行了呢？于是，我们可以尝试以下方法，同时对两个节点进行递归操作：
def connect_two_nodes(node1, node2):
# 基本条件，当节点不存在，直接返回
if not node1 or not node2:
return
# 第一步：对拥有同一父节点的两个兄弟节点进行直接连接
node1.next = node2
# 第二步：分别对两个节点的左右子节点进行递归连接
connect_two_nodes(node1.left, node1.right)
connect_two_nodes(node2.left, node2.right)
# 第三步：左边节点的右子节点 -> 右边节点的左子节点
connect_two_nodes(node1.right, node2.left)
def connect(root):
if not root: return None
connect(root.left, root.right)
return root除了递归，我们再使用层序遍历来解这道题。
对于上述问题，有两种连接方式：
- 连接1 → 两个节点具有共同的父节点，我们可以使用以下方式对这种情况进行连接：
node.left.next = node.right- 连接2 → 两个节点没有共同的父节点，但是可以通过第一个父节点的
next节点获取到第二个父节点，将第一个父节点的右孩子与第二个父节点的左孩子连接：
node.right.next = node.next.left完成当前的连接后，进入下一层重复操作，知道所有节点都已连接。进入下一层后需要先更新最左节点，然后从最左节点开始遍历该层节点。因为是完美二叉树，所以当最左节点的左孩子不在时，表明该层已经是最后一层，完成了所有节点的连接。
def connect(self, root):
if not root: return root
# 从根结点开始
leftmost = root
while leftmost.left:
# 遍历同一层节点链表
head = leftmost
while head:
# 连接具有统一父节点的两个左右子节点
head.left.next = head.right
# 如果两个节点相邻且没有共同父节点，那么可以通过父节点的 next 节点来连接
if head.next:
head.right.next = head.next.left
# 遍历到下一个节点，能运行到这里说明上一层操作中已经将本层的节点都已经连接好了
head = head.next
# 接下来对下一层进行操作
leftmost = leftmost.left
return root114
将二叉树展开为链表
我们可以抽象出以下两个流程：
- 将 root 的左右子树拉平
- 将左子树接到右边，左子树置为
None
- 将新的右子树的最右子节点连接原来的右子树
代码如下：
def flatten(self, root):
# base case
if not root:
return
# 拉平左右子树
self.flatten(root.left)
self.flatten(root.right)
# 暂存一下左右子树
left = root.left
right = root.right
# 将左子树接到右子树
root.right = left
# 将左子树置为 None
root.left = None
# 先选取旧左子树进行操作
tmp = root
# 找到旧左子树的最右子节点
while tmp.right:
tmp = tmp.right
# 将左子树的最右子节点连接右子树
tmp.right = right值得注意的是，我们需要对左右子树先进行
flatten 的递归操作，这一步的目的是拉平左右子树。当拉平左右子树后，我们就可以根据逻辑对左右子树进行连接和置换操作。