剑指 Offer 07. 重建二叉树
题目：剑指 Offer 07. 重建二叉树
解题思路1：
首先考虑前序遍历的特点，第一个节点是根节点；而后考虑中序遍历的结果，根节点左侧出现的均为左子树上的值，右侧的均为右子树上的值，然后由此在前序遍历中找到分界点进行递归，最终构建出整个树。（每次数组切片产生的开销过大。。强行增大了时间和空间）
时间：\(O(N)\)
空间：\(O(N^2)\)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
root = TreeNode(preorder[0])
r_pos = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:r_pos + 1], inorder[0:r_pos])
root.right = self.buildTree(preorder[r_pos + 1:], inorder[r_pos + 1:])
return root
优质解答1：递归（参考自K神）
新构建一个递归函数，只传入索引即可，并建立字典存储中序遍历中的索引以方便后续切分左右子树，其他与上述题解思路一样。（虽然思路一样，这代码的速度和内存的消耗差的太多了。。只能说K神yyds）
时间：\(O(N)\)
空间：\(O(N)\)
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def recur(root, left, right):
if left > right: return # 递归终止
node = TreeNode(preorder[root]) # 建立根节点
i = dic[preorder[root]] # 划分根节点、左子树、右子树
node.left = recur(root + 1, left, i - 1) # 开启左子树递归
node.right = recur(i - left + root + 1, i + 1, right) # 开启右子树递归
return node # 回溯返回根节点
dic, preorder = {}, preorder
for i in range(len(inorder)):
dic[inorder[i]] = i
return recur(0, 0, len(inorder) - 1)
优质解答2：迭代（参考自官方）
申请一个栈用于保存暂时未找到右孩子的节点，我们建一个指针ind_pre遍历前序的序列，用ind_in遍历中序序列，初始ind_pre=1,ind_in=0。因为根据前序遍历（根左右），以及中序遍历的序列中最开始的一定是树最左端的节点，如果此时栈顶节点不等于ind_in指向的节点，则代表ind_pre指向节点必为栈顶节点的左孩子，并将其入栈，ind_pre后移；如果此时栈顶元素等于ind_in指向的节点，则代表ind_pre指向节点必为栈内某一节点的右孩子，而栈中存储的节点顺序与它们在中序遍历中出现的顺序是相反的，所以以此和中序遍历进行对照，如果从一个节点处开始不满足逆序关系，则其在前序遍历中的前一个节点就为ind_pre的父节点。如果栈非空且栈顶节点与ind_in指针指向的元素相同（如果栈空了则默认最后一个出栈元素为其父节点），则弹栈，ind_in指针后移，继续比对，等找到一个栈顶节点与ind_in指向的节点不同时，我们知道前一个栈顶元素就是此时ind_pre指向节点的父节点，并且ind_pre是其右孩子，因为该节点也暂时未找到右孩子，所以将其入栈。如此往复，直到遍历结束。
时间：\(O(N)\)
空间：\(O(N)\)
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return
stack = []
root = TreeNode(preorder[0])
stack.append(root)
ind_in = 0
for ind_pre in range(1, len(preorder)) :
node = stack[-1]
if inorder[ind_in] != stack[-1].val:
new_node = TreeNode(preorder[ind_pre])
stack[-1].left = new_node
stack.append(new_node)
else:
while stack and stack[-1].val == inorder[ind_in]:
node = stack.pop()
ind_in += 1
node.right = TreeNode(preorder[ind_pre])
stack.append(node.right)
return root