二叉树

• 二叉树的种类：满二叉树、完全二叉树（底层从左到右是连续的）、二叉搜索树（有序数值）、平衡二叉搜索树（高度差的绝对值不超过1）
• 二叉树的存储方式：链式存储，顺序存储
• 二叉树遍历方式：
  • 深度优先搜索：前中后序遍历，中节点的位置对应这个前中后
  • 广度优先搜索：层次遍历
• 二叉树的定义（python版本）：

  class TreeNode:
  	def __init__(self, value):
  		self.value = value
  		self.left = None
  		self.right = None

几种遍历的示例：

• 前序遍历：ABDFGHIEC
• 中序遍历：FDHGIBEAC
• 后序遍历：FHIGDEBCA

递归法实现遍历

递归思想

递归的三要素：

• 明确递归终止条件；
• 给出递归终止时的处理办法；
• 提取重复的逻辑，缩小问题规模。

  简单题目

  # 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]:
          if not root:
              return []
          
          left = self.preorderTraversal(root.left)
          right = self.preorderTraversal(root.right)
  
          return [root.val] + left + right
  # 后序遍历
  class Solution:
      def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
          if not root:
              return []
          left = self.postorderTraversal(root.left)
          right = self.postorderTraversal(root.right)
          return left + right + [root.val]
  # 中序遍历
  """shenglve"""
  		return left + [root.val] + right

迭代法实现遍历

迭代法

注意栈的顺序，在循环没有停下来的时候如何选择放入节点的顺序，什么时候要将节点的数值放入结果中。

题目求解

# 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]:
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            # 弹出节点
            node = stack.pop()
            # 添加节点数值
            result.append(node.val)
            # 右节点 入栈
            if node.right:
                stack.append(node.right)
            # 左节点 入栈
            if node.left:
                stack.append(node.left)
        return result
# 中序遍历
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = []
        result = []
        cur = root
        while cur or stack:
            # 完成左节点的深度搜索
            if cur :
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                result.append(cur.val)
                cur = cur.right
        return result

# 后序遍历
	#前面部分跟前序一样，最后结果翻转
	return result[::-1]