關于樹，面試的時候多考察的是二叉樹

寬度優(yōu)先遍歷和深度優(yōu)先遍歷

# python3
from queue import Queue
class Solution:
    # 二叉樹的寬度優(yōu)先遍歷（層序遍歷）
    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)

其中深度優(yōu)先遍歷：

• 前序遍歷

  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)
  

這幾種遍歷算法又分為遞歸實現和循環(huán)實現，六種方法需要熟練掌握

其他二叉樹的特例：

• 二叉搜索樹——左子節(jié)點總是小于等于根節(jié)點，右子節(jié)點總是大于等于根節(jié)點，我們可以平均在O(logn)的時間內根據數值在二叉搜索樹中找到一個節(jié)點
• 堆——堆分為最小堆和最大堆，分別對應規(guī)則是根節(jié)點最小 和 根節(jié)點最大，用來快速獲取最值
• 紅黑樹——紅黑樹是把樹中的節(jié)點定義為紅、黑兩種顏色，并通過規(guī)則確保從根節(jié)點到葉節(jié)點的最長路徑的長度不超過最短路徑的兩倍。在C++的STL中，set、multiset、map、multimap等數據結構都是基于紅黑樹實現的

題目：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如，輸入前序遍歷序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍歷序列{4, 7, 2, 1, 5, 3, 8, 6}，則重建二叉樹。

class Solution:
    # 前序遍歷序列的第一個元素是二叉樹的根節(jié)點
    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