作者 | BoCong-Deng
題圖 | 視覺中國
出品 | CSDN博客
樹結構對于程序員來說應該不陌生，特別是二叉樹，基本只要接觸算法這一類的都一定會碰到的，所以我打算通過一篇文章，對二叉樹結構的相關算法進行總結匯總，思路和代碼實現相結合，讓你不在懼怕二叉樹。（ps：后面我還想寫一篇樹結構的高級篇，就是多叉數，就是對我平時看算法論文碰到的一些新奇的算法，比如B樹、B+樹，還有我一種叫做Bed樹的新奇算法等等）
單純就是想分享技術博文，還想說一句就是，如果覺得有用，請點個關注、給個贊吧，也算對我來說是個寬慰，畢竟也得掉不少頭發，嘿嘿嘿。
下面的思路講解中，我會給出一個類偽代碼的思路，然后進行相關說明，也就是一種思路框架，有了思路框架，以后碰到問題就直接交給框架完成。本文主要說一下二叉搜索樹（Binary Search Tree，簡稱 BST），BST是一種很常用的的二叉樹。它的定義是：一個二叉樹中，任意節點的值要大于等于左子樹所有節點的值，且要小于等于右邊子樹的所有節點的值。如下就是一個符合定義的 BST：
后面如果遇到特殊的思路結構，如多叉樹，我會特別說明。首先我們先給出二叉樹的節點定義（這個定義應該不陌生吧，有刷算法題都會碰到）。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
遞歸
不過這里要說明一點的是，在偽代碼中的“進行想要的操作”的位置，不一定就在我放置的位置，具體位置還需要我們根據不同的實際需求進行判斷。不過因為前中后序的遍歷，遞歸進入的時機應該需要和我的一樣。
先序遍歷
遍歷根節點，如果根節點為空，返回；否則，遍歷根節點，然后先序遍歷左子樹，再先序遍歷右子樹。
public void preorderTraverse(TreeNode root){
System.out.print(node.val+" ");
preorderTraverse(root.left);
preorderTraverse(root.right);
}
中序遍歷
路過根節點，如果根節點為空，返回；否則，中序遍歷左子樹，然后遍歷根節點，再中序遍歷右子樹。
public void inorderTraverse(TreeNode root){
inorderTraverse(root.left);
System.out.print(node.val+" ");
inorderTraverse(root.right);
}
后序遍歷
路過根節點，如果根節點為空，返回；否則，后序遍歷左子樹，再后序遍歷右子樹，最后遍歷根節點。
public void postorderTraverse(TreeNode root){
postorderTraverse(root.left);
postorderTraverse(root.right);
System.out.print(node.val+" ");
}
迭代（非遞歸）
我們使用迭代的思想，其實就是利用循環和棧來模擬遞歸的操作，上面遞歸的操作，其實就是一個不斷將自己以及左右子節點進行壓棧和出棧的過程，如果理解了上面的算法下面的算法就好理解了
前序遍歷
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>;
if(root==){
return list;
}
Stack<TreeNode> stack = new Stack<>;
stack.push(root);
while(!stack.isEmpty){
TreeNode res = stack.pop;
if(res.right != )
stack.push(res.right);
if(res.left != )
stack.push(res.left);
list.add(res.val);
}
return list;
}
中序遍歷
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>;
if(root==){
return list;
}
Stack<TreeNode> stack = new Stack<>;
TreeNode curr = root;
while(curr != || !(stack.isEmpty)){
if(curr!= ){
stack.push(curr);
curr = curr.left;
}else{
curr = stack.pop;
list.add(curr.val);
curr = curr.right;
}
}
return list;
}
后序遍歷
我們可以很簡單的實現另一種遍歷：”根->右->左“遍歷。雖然這種遍歷沒有名字，但是他是后序遍歷的反序。所以我們可以利用兩個棧，利用棧的LIFO特點，來實現后續遍歷。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>;
if(root==){
return list;
}
Stack<TreeNode> stack = new Stack<>;
stack.push(root);
while(!stack.isEmpty){
TreeNode res = stack.pop;
if(res.left != )
stack.push(res.left);
if(res.right != )
stack.push(res.right);
list.add(res.val);
}
list.reserve;
return list;
}
深度優先搜索（DFS）
其實，二叉樹的先序遍歷，中序遍歷，后序遍歷，都是深度優先搜索，深搜是一種思想，并不具體指代實現方式，你可以使用遞歸，也可以使用棧來實現，所以上面提到的都是深度優先搜索的實現方式，畢竟“深度優先”嘛。
那在這里我就是提幾個實際的應用的例子，加深一下印象。
二叉樹的最大深度
public int maxDepth(TreeNode root) {
if(root==){
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left,right)+1;
}
二叉樹的鏡像
public void Mirror(TreeNode root) {
if(root!=){
if(root.left!= || root.right!= ){
TreeNode temp =root.left;
root.left=root.right;
root.right=temp;
}
Mirror(root.left);
Mirror(root.right);
}
}
對稱二叉樹
boolean isSymmetrical(TreeNode pRoot){
if(pRoot == )
return true;
return real(pRoot.left,pRoot.right);
}
public boolean real(TreeNode root1,TreeNode root2){
if(root1 == && root2 == ){
return true;
}
if(root1 == || root2 == ){
return false;
}
if(root1.val != root2.val){
return false;
}
return real(root1.left,root2.right)&&real(root1.right,root2.left);
}
路徑總和
public class Solution {
private ArrayList<Integer> list = new ArrayList<Integer>;
private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>;
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == )
return listAll;
list.add(root.val);
target -= root.val;
if(target == 0 && root.left== && root.right == ){
listAll.add(new ArrayList<Integer>(list));
}
FindPath(root.left,target);
FindPath(root.right,target);
list.remove(list.size-1);
return listAll;
}
}
重建二叉樹
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
}
public TreeNode reConstructBinaryTree(int [] pre,int startpre,int endpre,int [] in,int startin,int endin){
if(startpre > endpre || startin > endin){
return ;
}
TreeNode root = new TreeNode(pre[startpre]);
for(int i =startin;i<=endin;i++){
if(in[i] == pre[startpre]){
root.left = reConstructBinaryTree(pre,startpre+1,startpre+i-startin,in,startin,i-1);
root.right = reConstructBinaryTree(pre,startpre+i-startin+1,endpre,in,i+1,endin);
}
}
return root;
}
二叉搜索樹的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == || root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left!= && right!=){
return root;
}
return left!=?left:right;
}
}
二叉樹的序列化和反序列化
序列化：
public String serialize(TreeNode root) {
if (root == ) {
return ;
}
// 利用二叉樹的層次遍歷方式進行序列化
StringBuilder res = new StringBuilder;
LinkedList<TreeNode> queue = new LinkedList<>;
queue.add(root);
while (!queue.isEmpty) {
TreeNode node = queue.remove;
if (node != ) {
res.Append(node.val).append(",");
queue.add(node.left);
queue.add(node.right);
} else {
res.append(",");
}
}
return res.toString;
}
反序列化：
public TreeNode deserialize(String data) {
if (data == || data.length == 0) {
return ;
}
String dataArr = data.split(",");
// 層次遍歷逆向還原二叉樹
int index = 0;
TreeNode root = toNode(dataArr[index]);
LinkedList<TreeNode> queue = new LinkedList<>;
queue.add(root);
while (index < dataArr.length - 2 && !queue.isEmpty) {
TreeNode cur = queue.remove;
// 添加左子節點
TreeNode leftNode = toNode(dataArr[++index]);
cur.left = leftNode;
// 隊列中的節點用于為其賦值孩子節點，若該節點本身為 ，
// 沒有孩子節點，便不再添加到隊列中，下同理
if (leftNode != ) {
queue.add(leftNode);
}
// 添加右子節點
TreeNode rightNode = toNode(dataArr[++index]);
cur.right = rightNode;
if (rightNode != ) {
queue.add(rightNode);
}
}
return root;
}
private TreeNode toNode(String val) {
if (!"".equals(val)) {
return new TreeNode(Integer.parseInt(val));
} else {
return ;
}
}
廣度優先搜索（BFS）
-
首先將根節點放入隊列中。
-
從隊列中取出第一個節點，并檢驗它是否為目標。
-
如果找到目標，則結束搜索并回傳結果。
-
否則將它所有尚未檢驗過的直接子節點加入隊列中。
-
若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜索的目標。結束搜索并回傳“找不到目標”。
-
重復步驟2。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>;
List<TreeNode> quene = new ArrayList<TreeNode>;
if(root == ){
return res;
}
quene.add(root);
while(quene.size!=0){
int count = quene.size;
List<Integer> list = new ArrayList<Integer>;
while(count>0){
TreeNode temp =quene.remove(0);
list.add(temp.val);
if(temp.left!=){
quene.add(temp.left);
}
if(temp.right!=){
quene.add(temp.right);
}
count--;
}
res.add(list);
}
return res;
}
莫里斯遍歷（Morris）
通常我們對于二叉樹進行遍歷時，使用遞歸遍歷或是基于棧來遍歷，這兩種方法都擁有最差為O(n)的空間復雜度(遞歸方法會在遞歸調用上浪費更多的時間)，以及O(n)的時間復雜度。對于時間復雜度來說，由于需要遍歷每個元素一次，所以O(n)已是最優情況。如此只能對空間進行優化。Morris遍歷如何做到的呢？首先我們需要分析遞歸和基于棧的遍歷它們為什么有O(n)的空間占用。以下圖這個簡單的二叉樹遍歷為例：
例如進行中序遍歷(LDR)，從1開始：
-
1有左孩子2，將1放入棧中，移動到節點2；
-
2有左孩子4，將2放入棧中，移動到節點4；
-
4左孩子為空，輸出節點4，此時節點4右孩子也為空，彈棧回到節點2；
-
輸出節點2，節點2有右孩子5，移動到節點5；
-
5左孩子為空，輸出節點5，此時節點5右孩子也為空，彈棧回到節點1；
…
從上面分析可以得知，傳統遍歷利用空間存儲未實現全部操作的父節點，比如對于1節點，一開始進行L操作，沒有進行D、R操作所以需要存儲起來。為解決這一問題，Morris算法用到了”線索二叉樹”的概念，利用葉節點的左右空指針指向某種遍歷順序的前驅節點或后繼節點。Morris算法中序遍歷流程：
-
設置節點1為Current節點；
-
Current節點不為空，且有左孩子，于是找到節點1左子樹中的最右側節點，即節點5，使其右孩子指針指向自己，即link1；
-
Current節點移動到左孩子節點2，并刪除父節點的左指針，使其指向為，即刪除erase1；
-
節點2不為空，且有左孩子，于是找到節點2左子樹中最右側節點，即節點4，使其右孩子指針指向自己，即link2；
-
Current節點移動到左孩子節點4，并刪除父節點的左指針，使其指向為，即刪除erase2；
-
節點4左孩子為空，輸出節點4，移動到右孩子節點2；
-
節點2無左孩子(指針指向)，輸出節點2，移動到右孩子節點5；
-
節點5無左孩子，輸出節點5，移動到右孩子節點1；
-
節點2無左孩子(指針指向)，輸出節點1，移動到右孩子節點3；
-
…
代碼實現：
void Morris_inorderTraversal(TreeNode root) {
TreeNode curr = root;
TreeNode pre;
while (curr != ) {
if (curr.left == ) { // 左孩子為空
System.out.print(curr.val+" ");
curr = curr.right;
}
else { // 左孩子不為空
// 找左子樹中的最右節點
pre = curr.left;
while (pre.right != ) {
pre = pre.right;
}
// 刪除左孩子，防止循環
pre.right = curr;
TreeNode temp = curr;
curr = curr.left;
temp.left = ;
}
}
}
AVL樹
AVL 樹是一種平衡二叉樹，平衡二叉樹遞歸定義如下：
-
左右子樹的高度差小于等于 1。
-
其每一個子樹均為平衡二叉樹。
為了保證二叉樹的平衡， AVL 樹引入了所謂監督機制，就是在樹的某一部分的不平衡度超過一個閾值后觸發相應的平衡操作。保證樹的平衡度在可以接受的范圍內。既然引入了監督機制，我們必然需要一個監督指標，以此來判斷是否需要進行平衡操作。這個監督指標被稱為“平衡因子（Balance Factor）”。定義如下：
-
平衡因子：某個結點的左子樹的高度減去右子樹的高度得到的差值。
基于平衡因子，我們就可以這樣定義 AVL 樹。
-
AVL 樹：所有結點的平衡因子的絕對值都不超過 1 的二叉樹。
為了計算平衡因子，我們自然需要在節點中引入高度這一屬性。在這里，我們把節點的高度定義為其左右子樹的高度的最大值。因此，引入了高度屬性的 AVL 樹的節點定義如下：
public class TreeNode {
int val;
int height;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
這里的節點和上面的不同的地方在于，我們多加了一個高度，用來記錄每個節點的高度，如何得到每個節點的高度很簡單，前面講的算法中任何一種思路都可以實現，我這里就不贅述了，不過這里要多說一點的是，與之對應地，我們在進行如下操作時需要更新受影響的所有節點的高度：
-
在插入結點時， 沿插入的路徑更新結點的高度值
-
在刪除結點時（delete），沿刪除的路徑更新結點的高度值
我們重新定義了節點之后，有了高度屬性，計算平衡因子的操作就得以很簡單的實現，也就是某個節點的平衡因子=左節點高度-右節點高度。
當平衡因子的絕對值大于 1 時，就會觸發樹的修正，或者說是再平衡操作。
樹的平衡化操作
二叉樹的平衡化有兩大基礎操作：左旋和右旋。左旋，即是逆時針旋轉；右旋，即是順時針旋轉。這種旋轉在整個平衡化過程中可能進行一次或多次，這兩種操作都是從失去平衡的最小子樹根結點開始的(即離插入結點最近且平衡因子超過1的祖結點)。其中，右旋操作示意圖如下
所謂右旋操作，就是把上圖中的 B 節點和 C 節點進行所謂“父子交換”。在僅有這三個節點時候，是十分簡單的。但是當 B 節點處存在右孩子時，事情就變得有點復雜了。我們通常的操作是：拋棄右孩子，將之和旋轉后的節點 C 相連，成為節點 C 的左孩子。這樣，對應的代碼如下。
TreeNode treeRotateRight(TreeNode root) {
TreeNode left = root.left;
root.left = left.right; // 將將要被拋棄的節點連接為旋轉后的 root 的左孩子
left.right = root; // 調換父子關系
left.height = Math.max(treeHeight(left.left), treeHeight(left.right))+1;
right.height = Math.max(treeHeight(right.left), treeHeight(right.right))+1;
return left;
}
而左旋操作示意圖如下
左旋操作和右旋操作十分類似，唯一不同的就是需要將左右互換下。我們可以認為這兩種操作是對稱的。代碼如下：
TreeNode treeRotateLeft(TreeNode root) {
TreeNode right = root.ight;
root.right = right.left;
right.left = root;
left.height = Math.max(treeHeight(left.left), treeHeight(left.right))+1;
right->height = Math.max(treeHeight(right.left), treeHeight(right.right))+1;
return right;
}
需要平衡的四種情況
-
LL 型
所謂 LL 型就是上圖左邊那種情況，即因為在根節點的左孩子的左子樹添加了新節點，導致根節點的平衡因子變為 +2，二叉樹失去平衡。對于這種情況，對節點 n 右旋一次即可。
-
RR 型
RR 型的情況和 LL 型完全對稱。只需要對節點 n 進行一次左旋即可修正。
-
LR 型
LR 就是將新的節點插入到了 n 的左孩子的右子樹上導致的不平衡的情況。這時我們需要的是先對 i 進行一次左旋再對 n 進行一次右旋。
-
RL 型
RL 就是將新的節點插入到了 n 的右孩子的左子樹上導致的不平衡的情況。這時我們需要的是先對 i 進行一次右旋再對 n 進行一次左旋。
這四種情況的判斷很簡單。我們根據破壞樹的平衡性（平衡因子的絕對值大于 1）的節點以及其子節點的平衡因子來判斷平衡化類型。
平衡化操作的實現如下：
int treeGetBalanceFactor(TreeNode root) {
if(root == )
return 0;
else
return x.left.height - x.right.height;
}
TreeNode treeRebalance(TreeNode root) {
int factor = treeGetBalanceFactor(root);
if(factor > 1 && treeGetBalanceFactor(root.left) > 0) // LL
return treeRotateRight(root);
else if(factor > 1 && treeGetBalanceFactor(root.left) <= 0) { //LR
root.left = treeRotateLeft(root.left);
return treeRotateRight(temp);
} else if(factor < -1 && treeGetBalanceFactor(root.right) <= 0) // RR
return treeRotateLeft(root);
else if((factor < -1 && treeGetBalanceFactor(root.right) > 0) { // RL
root.right = treeRotateRight(root.right);
return treeRotateLeft(root);
} else { // Nothing happened.
return root;
}
}
這里推薦一個AVL樹動態化的網站，可以通過動態可視化的方式理解AVL：
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
原文鏈接：
https://blog.csdn.net/DBC_121/article/details/104584060
