重建二叉树——jzoffer

关于树，面试的时候多考察的是二叉树

宽度优先遍历和深度优先遍历

# python3
from queue import Queue
class Solution:
    # 二叉树的宽度优先遍历（层序遍历）
    def layertraverse(self, root):
        # 1, 2, 3, 4, 5, 6, 7, 8
        que = Queue()
        que.put(root)
        while not que.empty():
            node = que.get()
            print(node.value)
            if node.left:
                que.put(node.left)
            if node.right:
                que.put(node.right)

其中深度优先遍历：

• 前序遍历

  class Solution:
      # 递归方法
      def recuristive(self, root):
          if root is not None:
              print(root.value)
              self.recuristive(root.left)
              self.recuristive(root.right)
      # 遍历方法
      def iterator(self, root):
          stack = [root]
          while len(stack) > 0:
              node = stack.pop()
              print(node.value)
              if node.right:
                  stack.append(node.right)
              if node.left:
                  stack.append(node.left)
  

• 中序遍历

  class Solution:
      # 递归方法
      def recuristive(self, root):
          if not root:
              self.recuristive(root.left)
              print(root.value)
              self.recuristive(root.right)
      # 遍历方法
      def iterator(self, root):
          # 4 7 2 1 5 3 8 6
          stack = []
          node = root
          while len(stack) > 0 or node:
              if node:
                  stack.append(node)
                  node = node.left
              else:
                  node = stack.pop()
                  print(node.value)
                  node = node.right  
  

• 后序遍历

  class Solution:
      # 递归方法
      def recuristive(self, root):
          if root:
              self.recuristive(root.left)
              self.recuristive(root.right)
              print(root.value)
              
      # 遍历方法
      def iterator(self, root):
          # 7 4 2 5 8 6 3 1
          stack_pre_right = [root]
          stack = []
          while len(stack_pre_right) > 0:
              node = stack_pre_right.pop()
              stack.append(node)
              if node.left:
                  stack_pre_right.append(node.left)
              if node.right:
                  stack_pre_right.append(node.right)
          while stack:
              node = stack.pop()
              print(node.value)
  

这几种遍历算法又分为递归实现和循环实现，六种方法需要熟练掌握

其他二叉树的特例：

• 二叉搜索树——左子节点总是小于等于根节点，右子节点总是大于等于根节点，我们可以平均在O(logn)的时间内根据数值在二叉搜索树中找到一个节点
• 堆——堆分为最小堆和最大堆，分别对应规则是根节点最小 和 根节点最大，用来快速获取最值
• 红黑树——红黑树是把树中的节点定义为红、黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。在C++的STL中，set、multiset、map、multimap等数据结构都是基于红黑树实现的

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建二叉树。

class Solution:
    # 前序遍历序列的第一个元素是二叉树的根节点
    def func(self, mid_seq, pre_seq):
        mid_dict = {value: index for index, value in enumerate(mid_seq)}
        return self.create_tree(mid_dict, mid_seq, 0, len(mid_seq)-1, pre_seq, 0, len(pre_seq)-1)
    
    def create_tree(self, mid_dict, mid_seq, mid_beg, mid_end, pre_seq, pre_beg, pre_end):
        if mid_beg > mid_end or pre_beg > pre_end:
            return None
        root = TreeNode()
        root.value = pre_seq[pre_beg]
        
        mid = mid_dict[pre_seq[pre_beg]]
        num = mid - mid_beg
        
        root.left = self.create_tree(mid_dict, mid_seq, mid_beg, mid-1, pre_seq, pre_beg+1, pre_beg+num)
        root.right = self.create_tree(mid_dict, mid_seq, mid+1, mid_end, pre_seq, pre_beg+num+1, pre_end)
        return root