文字長度: ★★★☆☆
閱讀難度: ★★☆☆☆
原創程度: ★★★★★
前言
樹是一種資料結構，二叉樹是一種特殊的樹，二叉搜尋樹是一種特殊的二叉樹。本文總結了二叉樹/二叉搜尋樹中我認為最經典的一些題目，比較複雜的配了圖來幫助了解。
目錄-----加【】的是題目
- 樹基本概念
- 深度
- 高度
- 層
- 葉子
- 二叉樹
- 周遊序列
- 【前序周遊】iterative解法
- 【中序周遊】iterative解法
- 【後序周遊】iterative解法
- 【給中序+前序，還原二叉樹】(1) recursive解法; (2) iterative解法
- 【給二叉樹，求層次周遊序列】BFS解法
- 平衡樹
- 【判斷是否是平衡樹】
- 後繼結點/前驅結點
- 【求後繼結點】(1) 知道parent; (2)不知道parent
- 周遊序列
- 二叉搜尋樹 (BST)
- 查詢
- 【BST中查詢某值】
- 【BST的最大/小值】
- 結點變換
- 【移植子樹】
- 【BST中插入一個結點】
- 【BST中删除一個結點】(1) iterative解法; (2) recursive解法
- 構造
- 【從有序數組中建構平衡的BST】(1) recursive解法; (2) iterative解法
- 查詢
1. 所有樹都有的屬性
【深度】對于某個結點而言，其深度(depth)就是從樹的根結點到該結點的路徑長度，即經過的結點數量（包括根結點但不包括自己），根結點的深度是0。孩子的深度=自己的深度+1。
相關考題 : 求樹中某個結點的深度
- 思路: DFS和BFS都可以
: 樹中任意結點的深度的最大值，也即樹中任意葉子的深度的最大值。
相關考題: 求樹的高度
- 思路: DFS和BFS都可以
: 所有擁有深度y的結點組成的集合稱作樹的level-y，根結點在level-0
【葉子】: 沒有孩子結點的結點
2. 二叉樹特有的屬性名詞
【周遊序列】分為前序周遊序列，中序周遊序列，後序周遊序列，層次周遊序列。這部分典型的知識點包括: 寫出
- 前序周遊 (Preorder Traversal) 不用遞歸的寫法
vector
- 中序周遊 (Inorder Traversal) 不用遞歸的寫法
vector
- 後序周遊 (Postorder Traversal) 不用遞歸的寫法
vector
1. 給定前序+中序，還原二叉樹(或者求後序，本質沒差别)
- Recursive解法: 解題的核心要點是: preorder的第一個一定是根；inorder的根結點左邊是左子樹，右邊是右子樹。
- 時間複雜度: O(N^2) （對每個結點都要搜尋，共n個結點）
- 空間複雜度: 除了遞歸棧，使用了O(1) 輔助空間
TreeNode
- Iterative解法: 這個解法比較 優雅
- 時間複雜度: O(N)
- 空間複雜度: O(N)
- 将前序周遊的結點依次入棧，同時後一個結點作為前一個結點的左孩子，不斷疊加。
- 如果前序周遊目前結點等于中序周遊的目前結點，出棧結點直到和中序周遊的結點不相等。并且同時設定flag為true，來标記做了一次pop操作。
- 重複上述過程直到前序周遊的棧為空。
- 核心要點 是
- 隻有preorder序列入棧操作時會在樹中插入新結點
- flag為true時，插入新結點到上一個結點的右孩子位置，并且reset flag.
TreeNode
2. 給定後序+中序，還原二叉樹
- 和前序+中序一樣，隻不過postorder的最後一個結點一定是根
給定二叉樹，求層次周遊序列
- 經典的BFS解法
vector
任意節點的子樹的高度差都小于等于1
相關考題 : 判斷一個給定的二叉樹是否是平衡樹
bool
(successor) 在給定二叉搜尋樹中，求某結點的中序周遊的後繼結點
相關考題 : 給定一個二叉搜尋樹，求某結點的中序周遊的後繼結點的值
- 如果該結點有右孩子，那麼就傳回右孩子的最小結點( 時間複雜度O(logN) )；否則返中序周遊中在自己後面并且最接近自己的祖先(找到結點的最近(層數差距最小)的祖先，使得該結點所在的子樹是該祖先的左孩子) 。中序周遊中在自己後面并且最接近自己的祖先的求法分2種情況
- 第一種：二叉搜尋樹的結點 有指向parent的指針 ，那麼找到該祖先的方式是從該結點出發，向上搜尋直到找到滿足條件的祖先。
- 時間複雜度: O(logN)
- 第一種：二叉搜尋樹的結點 有指向parent的指針 ，那麼找到該祖先的方式是從該結點出發，向上搜尋直到找到滿足條件的祖先。
/**
- 第二種：二叉搜尋樹的結點 沒有指向parent的指針 ，那麼找到該祖先的方式是從root出發，用一個指針curr去找該結點p，另一個指針succ用來記錄目前值最小的祖先，如果遇到一個大于p的值的祖先，succ指針就指向之前的curr，curr指向它的左孩子。
- 時間複雜度: O(N)
第二種情況示意圖
TreeNode
: 和“後繼結點”相應，做對稱操作即可
3. 二叉搜尋樹的基本操作
【查詢】給定二叉搜尋樹中是否存在值為x的結點。查詢是二叉搜尋樹最基本的操作。
TreeNode
- 變種題: 給定二叉搜尋樹中是否存在值為x的結點，如果存在，傳回該結點到根的距離，如果不存在傳回-1
TreeNode
【
最大/小值查詢】: 求給定二叉搜尋樹的最大/小值
TreeNode
【
移植】将某個樹v移植到樹root的結點u處
TreeNode
在一個二叉搜尋樹中插入一個結點。注意，被插入的結點必然是一個“葉子”結點
TreeNode
: 在一個二叉搜尋樹中删除一個值為x的結點，如果該值不存在，則傳回原來的樹
删除一個結點比插入結點複雜很多，因為被删除的結點可能不是“葉子”結點。我們具體分為3種情況讨論:
- 如果被删除的結點隻有左子樹，那麼就用p的左孩子移植到p的位置
- 如果被删除的結點隻有右子樹，那麼就用p的右孩子移植到p的位置
- 如果被删除的結點有左右2個子樹，那麼需要找到右子樹中最小的結點x，将它放到p的位置。由于x肯定沒有左子樹（否則不會是子樹上最小的結點），但是可能有右子樹。是以移動x到p之前，需要先把x從子樹上删除。
// iterative 思路
- 另外還有一個 recursive 的思路:
- 如果目前結點就是需要被删除的結點
- 如果沒有右孩子，就是把目前結點删除
- 如果有右孩子，将右子樹上的最小結點和目前結點的值交換，再去删除右子樹上的該值
- 如果目前結點的值大于需要被删除的值，那麼被删除的值在左子樹上
- 如果目前結點的值小于需要被删除的值，那麼被删除的值在右子樹上
- 如果目前結點就是需要被删除的結點
// recursive 思路
【
構造】從一個有序數組，建構平衡的二叉搜尋樹
- recursive思路: 很直覺，不需要多說
- 時間複雜度: O(N) ，顯然每個結點對應調用了一次buildBST函數
- 空間複雜度: 即遞歸棧深度， O(logN)
TreeNode
- iterative: 由于從有序數組建構BST是一個深度優先周遊的問題，是以iterative的解法用棧來解決。
- 時間複雜度: O(N) ，顯然是周遊了一遍數組
- 空間複雜度: 即壓棧最深的深度，也即樹的高度， O(logN)
TreeNode