第6課-樹、二叉樹、二叉搜尋樹

文章目錄

• 樹 Tree
• 二叉樹 Binary Tree
• 圖 Graph
• 示例代碼
• 二叉樹周遊 Pre-order/In-order/Post-order
• • 示例代碼
• 二叉搜尋樹 Binary Search Tree
• 二叉搜尋樹 Binary Search Tree
• 二叉搜尋樹常見操作
• 複雜度分析
• 樹的面試題解法一般都是遞歸
• • 示例代碼
  • 示例代碼
• 樹的周遊 DEMO
• 實戰題目

樹 Tree

二叉樹 Binary Tree

圖 Graph

• Linked List 是特殊化的 Tree
• Tree 是特殊化的 Graph

示例代碼

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

Java
public class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int val) {
   this.val = val;
   this.left = null;
   this.right = null;
  } 
}
           

C++
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}
           

二叉樹周遊 Pre-order/In-order/Post-order

1.前序(Pre-order):根-左-右

2.中序(In-order):左-根-右

3.後序(Post-order):左-右-根

示例代碼

def preorder(self, root):
  if root:
    self.traverse_path.append(root.val)
    self.preorder(root.left)
    self.preorder(root.right)
def inorder(self, root):
  if root:
    self.inorder(root.left)
    self.traverse_path.append(root.val)
    self.inorder(root.right)
def postorder(self, root):
  if root:
    self.postorder(root.left)
    self.postorder(root.right)
    self.traverse_path.append(root.val)
           

二叉搜尋樹 Binary Search Tree

二叉搜尋樹 Binary Search Tree

二叉搜尋樹，也稱二叉搜尋樹、有序二叉樹(Ordered Binary Tree)、 排序二叉樹(Sorted Binary Tree)，是指一棵空樹或者具有下列性質的 二叉樹:

1. 左子樹上所有結點的值均小于它的根結點的值;
2. 右子樹上所有結點的值均大于它的根結點的值;
3. 以此類推:左、右子樹也分别為二叉查找樹。 (這就是 重複性!)

中序周遊:升序排列

二叉搜尋樹常見操作

1. 查詢
2. 插入新結點(建立)
3. 删除

Demo: https://visualgo.net/zh/bst

複雜度分析

樹的面試題解法一般都是遞歸

為什麼?

示例代碼

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

           

Java
public class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int val) {
   this.val = val;
   this.left = null;
   this.right = null;
  }
}
           

C++
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}
           

示例代碼

def preorder(self, root):
  if root:
    self.traverse_path.append(root.val)
    self.preorder(root.left)
    self.preorder(root.right)
def inorder(self, root):
  if root:
    self.inorder(root.left)
    self.traverse_path.append(root.val)
    self.inorder(root.right)
def postorder(self, root):
  if root:
    self.postorder(root.left)
    self.postorder(root.right)
    self.traverse_path.append(root.val)
           

樹的周遊 DEMO

實戰題目

1. https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
2. https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
3. https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
4. https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
5. https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/