※5.1.4.4.1

5.1二叉樹

class Node<V>{
V value;
Node left;
Node right;
}

用遞歸和非遞歸兩種方式實(shí)現(xiàn)二叉樹的先序、中序、后序遍歷
如何直觀的打印一顆二叉樹
如何完成二叉樹的寬度優(yōu)先遍歷（常見題目：求一顆二叉樹的寬度）

5.1.1例1：用遞歸和非遞歸兩種方式實(shí)現(xiàn)二叉樹的先序、中序、后序遍歷

遞歸序是通過遞歸方法生成的序列，而非遞歸序則是通過循環(huán)和棧的輔助實(shí)現(xiàn)的序列。兩者在序列化順序上是一致的，都是按照 “根結(jié)點(diǎn)、左子樹、右子樹” 的順序遍歷二叉樹。

5.1.1.1遞歸序的先序、中序、后序遍歷

先序遍歷：

頭左右
對于所有子樹來說，先打印頭節(jié)點(diǎn)，再打印左子樹上的所有節(jié)點(diǎn)，再打印右樹上的所有節(jié)點(diǎn)（對于每一個(gè)子樹都是先打印左，后打印右）
1，2，4，5，3，6，7
第一次碰到的就打印，不是就不打印

中序遍歷：

左頭右
先打印左樹，再打印頭，再打印右樹
4，2，5，1，6，3，7
利用遞歸序，第二次再打印，不是第二次什么也不做

后序遍歷：

左右頭
先打印左樹，再打印右樹，再打印頭
4，5，2，6，7，3，1
利用遞歸序，第三次再打印，不是第三次什么也不做

#include <iostream>using namespace std;// 定義二叉樹的結(jié)點(diǎn)
struct Node {int data;Node* left;Node* right;
};// 創(chuàng)建一個(gè)新的二叉樹結(jié)點(diǎn)
Node* createNode(int data) {Node* newNode = new Node();if (newNode == nullptr) {cout << "內(nèi)存分配失敗!" << endl;return nullptr;}newNode->data = data;newNode->left = nullptr;newNode->right = nullptr;return newNode;
}// 先序遍歷
void preorderTraversal(Node* root) {if (root == nullptr)return;cout << root->data << " ";preorderTraversal(root->left);preorderTraversal(root->right);
}// 中序遍歷
void inorderTraversal(Node* root) {if (root == nullptr)return;inorderTraversal(root->left);cout << root->data << " ";inorderTraversal(root->right);
}// 后序遍歷
void postorderTraversal(Node* root) {if (root == nullptr)return;postorderTraversal(root->left);postorderTraversal(root->right);cout << root->data << " ";
}int main() {// 創(chuàng)建二叉樹Node* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);root->right->left = createNode(6);root->right->right = createNode(7);// 輸出先序遍歷cout << "先序遍歷結(jié)果：" << endl;preorderTraversal(root);cout << endl;// 輸出中序遍歷cout << "中序遍歷結(jié)果：" << endl;inorderTraversal(root);cout << endl;// 輸出后序遍歷cout << "后序遍歷結(jié)果：" << endl;postorderTraversal(root);cout << endl;return 0;
}

5.1.1.2非遞歸序的先序、中序、后序遍歷

先序遍歷：

頭左右
1，2，4，5，3，6，7
每次把頭節(jié)點(diǎn)放入棧里，從棧中彈出一個(gè)節(jié)點(diǎn)cur，打印（處理）cur，先右邊放入棧中，再左邊放入棧中，從頭（從棧中彈出一個(gè)節(jié)點(diǎn)cur）開始周而復(fù)始
先放頭1節(jié)點(diǎn)，彈出1打印
放入右節(jié)點(diǎn)3，放入左節(jié)點(diǎn)2，彈出2打印
先放入5節(jié)點(diǎn)，再放入4節(jié)點(diǎn)，彈出4打印，
先放右再放左，都沒有所以什么也不做，彈出5打印
先放右再放左，都沒有所以什么也不做，彈出3打印
先放右節(jié)點(diǎn)7，再放左節(jié)點(diǎn)6，彈出6打印
先放右再放左，都沒有所以什么也不做，彈出7打印

中序遍歷：

左頭右
每棵樹左邊界進(jìn)棧，依次彈出節(jié)點(diǎn)的過程中打印，對彈出節(jié)點(diǎn)的右樹循環(huán)周而復(fù)始
1，2，4進(jìn)棧
彈出4打印4，沒有右樹
彈出2，打印2，有右樹5，壓棧5
彈出5，打印5，沒有右樹
彈出1，打印1，有右樹，壓棧3，6
彈出6，打印6，沒有右樹
彈出3，打印3，有右樹，壓棧7
彈出7，打印7
4，2，5，1，6，3，7

放入棧的順序是從頭到左，彈出棧的順序是左頭，之后取右樹再次先左再頭……

后序遍歷：

左右頭
放入到棧中是頭右左，
從收棧彈出反轉(zhuǎn)變成了左右頭
4，5，2，6，7，3，1

彈，cur
cur放入收棧
先左再右
循環(huán)

先壓棧頭1節(jié)點(diǎn)，彈出1節(jié)點(diǎn)壓棧到收棧
壓棧2，壓棧3，彈出3，3壓棧到收棧
壓棧6，壓棧7，彈出7，7壓棧到收棧
壓棧左右為空，彈出6，6壓棧到收棧
壓棧左右為空，彈出2，2壓棧到收棧
壓棧4，壓棧5，彈出5，5壓棧到收棧
壓棧左右為空，彈出4，4壓棧到收棧

彈出收棧4，5，2，6，7，3，1

#include <iostream>
#include <stack>using namespace std;// 定義二叉樹的結(jié)點(diǎn)
struct Node {int data;Node* left;Node* right;
};// 創(chuàng)建一個(gè)新的二叉樹結(jié)點(diǎn)
Node* createNode(int data) {Node* newNode = new Node();if (newNode == nullptr) {cout << "內(nèi)存分配失敗!" << endl;return nullptr;}newNode->data = data;newNode->left = nullptr;newNode->right = nullptr;return newNode;
}// 非遞歸先序遍歷
void iterativePreorderTraversal(Node* root) {if (root == nullptr)return;stack<Node*> st;st.push(root);while (!st.empty()) {Node* curr = st.top();st.pop();cout << curr->data << " ";if (curr->right)st.push(curr->right);if (curr->left)st.push(curr->left);}
}// 非遞歸中序遍歷
void iterativeInorderTraversal(Node* root) {if (root == nullptr)return;stack<Node*> st;Node* curr = root;while (curr != nullptr || !st.empty()) {while (curr != nullptr) {st.push(curr);curr = curr->left;}curr = st.top();st.pop();cout << curr->data << " ";curr = curr->right;}
}// 非遞歸后序遍歷
void iterativePostorderTraversal(Node* root) {if (root == nullptr)return;stack<Node*> st1, st2;st1.push(root);while (!st1.empty()) {Node* curr = st1.top();st1.pop();st2.push(curr);if (curr->left)st1.push(curr->left);if (curr->right)st1.push(curr->right);}while (!st2.empty()) {Node* curr = st2.top();st2.pop();cout << curr->data << " ";}
}int main() {// 創(chuàng)建二叉樹Node* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);root->right->left = createNode(6);root->right->right = createNode(7);// 輸出非遞歸先序遍歷cout << "非遞歸先序遍歷結(jié)果：" << endl;iterativePreorderTraversal(root);cout << endl;// 輸出非遞歸中序遍歷cout << "非遞歸中序遍歷結(jié)果：" << endl;iterativeInorderTraversal(root);cout << endl;// 輸出非遞歸后序遍歷cout << "非遞歸后序遍歷結(jié)果：" << endl;iterativePostorderTraversal(root);cout << endl;return 0;
}

5.1.2例2：如何直觀的打印一顆二叉樹

如第三個(gè)樹

5.1.3例3：如何完成二叉樹的寬度優(yōu)先遍歷

先序遍歷就是深度優(yōu)先遍歷

寬度遍歷用隊(duì)列（廣度優(yōu)先遍歷），頭進(jìn)尾出（先進(jìn)先出）彈出就打印

廣度優(yōu)先遍歷代碼

#include <iostream>
#include <queue>using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 寬度優(yōu)先搜索遍歷函數(shù)
void BFS(TreeNode* root) {if (root == nullptr) return;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();cout << node->val << " ";  // 打印出隊(duì)節(jié)點(diǎn)的值if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}
}int main() {// 構(gòu)建二叉樹TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);cout << "BFS traversal: ";BFS(root);return 0;
}

深度優(yōu)先遍歷代碼

void DFS(TreeNode* node) {if (node == nullptr)return;cout << node->val << " ";  // 打印當(dāng)前節(jié)點(diǎn)的值DFS(node->left);  // 遞歸遍歷左子樹DFS(node->right);  // 遞歸遍歷右子樹
}

5.1.3.1求一顆二叉樹的寬度

5.1.3.1.1方法1隊(duì)列哈希表方法

需要知道哪一層的節(jié)點(diǎn)個(gè)數(shù)，準(zhǔn)備一張表，記錄任何一個(gè)點(diǎn)在第幾層

當(dāng)前在哪一層 curLevel
當(dāng)前層發(fā)現(xiàn)幾個(gè)節(jié)點(diǎn) curLevelNodes
所有層中那一層節(jié)點(diǎn)數(shù)最多 max

5.1.3.1.2方法2隊(duì)列方法

NodeCurend=1
Nodenextend=null
int Curlevel=0

讓1節(jié)點(diǎn)進(jìn)隊(duì)列
彈出1節(jié)點(diǎn)先讓左孩子進(jìn)棧，看Nodenextend是否為空，如果為空，把Nodenextend設(shè)置為進(jìn)棧的節(jié)點(diǎn)2
再讓右孩子3進(jìn)棧，Nodenextend=3，int Curlevel=1
當(dāng)前節(jié)點(diǎn)是不是當(dāng)前層最后一個(gè)節(jié)點(diǎn)，是max=1，讓NodeCurend拷貝Nodenextend，NodeCurend=3，使Nodenextend=null，讓int Curlevel=0

彈出2節(jié)點(diǎn)，讓2節(jié)點(diǎn)的左孩子進(jìn)棧，再讓右孩子4進(jìn)棧，但是左孩子是nullptr，，所以4進(jìn)棧，int Curlevel=1
彈出3節(jié)點(diǎn)，讓3節(jié)點(diǎn)的左孩子5進(jìn)棧，再讓右孩子6進(jìn)棧，Nodenextend=6（當(dāng)前層誰最后進(jìn)棧誰是Nodenextend），int Curlevel=2，當(dāng)前層后面不會(huì)進(jìn)了max=2，NodeCurend拷貝Nodenextend，NodeCurend=6，使Nodenextend=null，讓int Curlevel=0

彈出4節(jié)點(diǎn)，讓4節(jié)點(diǎn)的左孩子進(jìn)棧，再讓右孩子進(jìn)棧，但是左右孩子都是nullptr，int Curlevel=1
彈出5節(jié)點(diǎn)，讓5節(jié)點(diǎn)的左孩子7進(jìn)棧，再讓右孩子進(jìn)棧，但是右孩子是nullptr，Nodenextend=7，int Curlevel=2
彈出6節(jié)點(diǎn)，讓6節(jié)點(diǎn)的左孩子進(jìn)棧，再讓右孩子8進(jìn)棧，但是左孩子是nullptr，Nodenextend=8，int Curlevel=3，6節(jié)點(diǎn)為本層的結(jié)束max=3，NodeCurend拷貝Nodenextend，NodeCurend=8，使Nodenextend=null，讓int Curlevel=0

……

5.1.4例4：二叉樹的相關(guān)概念及其實(shí)現(xiàn)判斷

5.1.4.1判斷一顆二叉樹是否是搜索二叉樹（BST）？

搜索二叉樹（Binary Search Tree，簡稱BST）是一種具有特殊性質(zhì)的二叉樹。它滿足以下定義：

每個(gè)節(jié)點(diǎn)都包含一個(gè)鍵（key）和一個(gè)相關(guān)聯(lián)的值（value）。
對于任意節(jié)點(diǎn)，其左子樹中的所有鍵的值都小于該節(jié)點(diǎn)的鍵的值。
對于任意節(jié)點(diǎn)，其右子樹中的所有鍵的值都大于該節(jié)點(diǎn)的鍵的值。
左子樹和右子樹都是搜索二叉樹。
也就是說，對于搜索二叉樹中的任意節(jié)點(diǎn)，其左子樹中的所有節(jié)點(diǎn)的鍵都小于該節(jié)點(diǎn)的鍵，而右子樹中的所有節(jié)點(diǎn)的鍵都大于該節(jié)點(diǎn)的鍵。這個(gè)特點(diǎn)使得搜索二叉樹有很好的查找和排序性能，在許多應(yīng)用中被廣泛使用。

中序遍歷

使用中序遍歷，如果輸出結(jié)果一直在升序，那它一定是搜索二叉樹

#include <limits>
int preValue = std::numeric_limits<int>::min();bool checkBST(Node* head)
{if (head == nullptr){return true;}bool isLeftBST = checkBST(head->left);if (!isLeftBST)//發(fā)現(xiàn)左樹不是搜索二叉樹就直接返回false{return false;}if (head->data <= preValue)//和上次搜索到值相比較，小于等于就返回false{return false;}else//大于就使preValue等于當(dāng)前值，下次循環(huán)就可以判斷了{preValue = head->data;}return checkBST(head->right);
}

次一點(diǎn)的方法

非遞歸方式

5.1.4.2判斷二叉樹是否是完全二叉樹（CBT）？

完全二叉樹（Complete Binary Tree）是一種特殊的二叉樹結(jié)構(gòu)（除了最后一層都是滿的，最后一層即便不滿，也是從左到右依次滿的）

（1）任一節(jié)點(diǎn)，一旦有右無左直接輸出false
（2）在（1）不違規(guī)條件下，如果遇到左右兩個(gè)孩子不雙全的情況，接下來遇到的所有節(jié)點(diǎn)都必須是葉節(jié)點(diǎn)

5.1.4.3判斷一顆二叉樹是否是滿二叉樹？

麻煩做法：
先求二叉樹最大深度L，再求二叉樹節(jié)點(diǎn)個(gè)數(shù)N
最大深度L和節(jié)點(diǎn)個(gè)數(shù)N滿足:N=2^L-1
如果滿足此關(guān)系必定是滿二叉樹，如果是滿二叉樹必定滿足此關(guān)系

5.1.4.4判斷一棵二叉樹是否是平衡二叉樹？

平衡二叉樹：對于任一子樹來說，左樹和右樹的高度差不超過1

※5.1.4.5判斷是搜索二叉樹、滿二叉樹、平衡二叉樹的遞歸套路（可以解決一切樹形DP問題）

樹形DP問題是面試題內(nèi)最難的二叉樹類型的問題了
都是基于怎么向左樹要信息，怎么向右樹要信息

※判斷是否是平衡二叉樹？

左樹需要返回是否平衡，高度是多少，右樹也相同

#include<cmath>
class ReturnType
{
public:bool isBalanced;int height;ReturnType(bool isB, int hei)//構(gòu)造函數(shù){isBalanced = isB;height = hei;}
};ReturnType* process(Node* x)
{if (!x) return new ReturnType(true, 0);//x為空的時(shí)候返回哪兩個(gè)值（是否是平衡樹true，高度0）ReturnType leftData = *process(x->left);ReturnType rightData = *process(x->right);int height = max(leftData.height, rightData.height) + 1;//左樹和右樹高度較大的一個(gè)加1bool isBalanced = leftData.isBalanced && rightData.isBalanced && abs(leftData.height - rightData.height) < 2;//左樹是平衡樹，右樹是平衡樹，左樹和右樹的差的絕對值小于2ReturnType* ans = new ReturnType(isBalanced, height);//最后返回的值（以x為頭的是否是平衡二叉樹，高度）return ans;
}bool isBalanced(Node* head)
{return process(head)->isBalanced;
}

※判斷是否是搜索二叉樹？

需要左樹是搜索二叉樹，左樹最大值max
需要右樹是搜索二叉樹，右樹最小值min
左樹最大值max < x（頭節(jié)點(diǎn)）
右樹最小值min > x（頭節(jié)點(diǎn)）
現(xiàn)在需求不一樣，但是必須每一個(gè)節(jié)點(diǎn)的需求是一樣的才是遞歸

//是否是搜索二叉樹？
class ReturnData
{
public:bool isBST;//根據(jù)需求要三個(gè)信息int min;int max;ReturnData(bool is,int mi,int ma)//構(gòu)造函數(shù){isBST = is;min = mi;max = ma;}
};
ReturnData* process(Node* x)
{if (!x)return nullptr;ReturnData* leftData = process(x->left);//默認(rèn)左樹給我一個(gè)信息ReturnData* rightData = process(x->right);//默認(rèn)右樹給我一個(gè)信息int Min = x->data;int Max = x->data;if (leftData!=nullptr)//如果左邊得到的信息不為空，則有東西{Min = std::min(Min, leftData->min);//如果左樹不為空，則左樹值和x（或當(dāng)前值）比大小，取最小值，找到左樹最小值Max = std::max(Max, leftData->max);//如果左樹不為空，則左樹值和x（或當(dāng)前值）比大小，取最大值，找到左樹最大值}if (rightData != nullptr){Min = std::min(Min, rightData->min);//如果右樹不為空，則左樹值和x（或當(dāng)前值）比大小，取最小值，找到右樹最小值Max = std::max(Max, rightData->max);//如果右樹不為空，則左樹值和x（或當(dāng)前值）比大小，取最大值，找到右樹最大值}bool isBST = true;//整棵樹書否是搜索二叉樹，默認(rèn)是//左邊不是搜索二叉樹了，返回false。左邊最大值大于x了，返回falseif (leftData != nullptr && (!leftData->isBST || leftData->max >= x->data)){isBST = false;}//右邊不是搜索二叉樹了，返回false。右邊最小值小于x了，返回falseif (rightData != nullptr && (!rightData->isBST || x->data >= rightData->min)){isBST = false;}return new ReturnData(isBST, Min, Max);//需求給了三個(gè)信息，返回三個(gè)值
}
bool isBST(Node* x)
{return process(x)->isBST;
}

※判斷是否是滿二叉樹？

需知整棵樹高度和節(jié)點(diǎn)個(gè)數(shù)

//是否是滿二叉樹？
class Info
{
public:int height;int nodes;Info(int h,int n){height = h;nodes = n;}
};Info* process(Node* x)
{if (!x)return new Info(0, 0);Info* leftData = process(x->left);Info* rightData = process(x->right);int height = max(leftData->height, rightData->height) + 1;int nodes = leftData->nodes + rightData->nodes + 1;return new Info(height, nodes);
};bool isF(Node* head){if (!head)return true;Info* data = process(head);return data->nodes == (1 << data->height - 1);//相當(dāng)于2^L-1}

5.1.5例5：最低公共祖先節(jié)點(diǎn)

給定兩個(gè)二叉樹的節(jié)點(diǎn)node1和node2找到他們的最低公共祖先節(jié)點(diǎn)

往上走，哪一個(gè)點(diǎn)是最初匯聚的點(diǎn)，第一個(gè)匯聚的點(diǎn)就是最低公共祖先

如E和F的最低公共祖先為E
如D和I的最低公共祖先為A

5.1.5.1方法1

往上遍歷過程生成一個(gè)鏈，用容器記錄鏈，在另一節(jié)點(diǎn)向上遍歷時(shí)走到容器記錄過的節(jié)點(diǎn)即為最低公共祖先
需要二叉樹頭，兩個(gè)節(jié)點(diǎn)

#include<iostream>
#include<map>
#include<set>
#include <unordered_map>using namespace std;struct Node {int value;Node* left;Node* right;Node(int x) : value(x), left(nullptr), right(nullptr) {}
};void process(Node* head, map<Node*, Node*>* fatherMap) {if (!head) return;fatherMap->insert(make_pair(head->left, head));fatherMap->insert(make_pair(head->right, head));process(head->left, fatherMap);//記錄左兒子和父節(jié)點(diǎn)process(head->right, fatherMap);//記錄右兒子和父節(jié)點(diǎn)
}//o1和o2一定屬于head為頭的樹
//返回o1和o2的最低公共祖先
Node* lca(Node* head, Node* o1, Node* o2) {auto* fatherMap = new map<Node*, Node*>();fatherMap->insert(make_pair(head, head));//設(shè)置head的父節(jié)點(diǎn)自己process(head, fatherMap);auto* set1 = new set<Node*>();//記錄下o1往上整條鏈的節(jié)點(diǎn)set1->insert(o1);//先放入o1Node* cur = o1;//當(dāng)前節(jié)點(diǎn)來到o1位置//o1經(jīng)過的節(jié)點(diǎn)都放入set1中while (cur != fatherMap->find(cur)->second) {set1->insert(cur);cur = fatherMap->find(cur)->second;}set1->insert(head);cur = o2;//o2經(jīng)過的節(jié)點(diǎn)都放入set1中，并且每經(jīng)過一個(gè)點(diǎn)，都看在不在set中while (cur != fatherMap->find(cur)->second) {if (set1->find(cur) != set1->end())return cur;else {cur = fatherMap->find(cur)->second;}}return head;
}int main() {Node* head = new Node(8);head->left = new Node(6);head->right = new Node(10);head->left->left = new Node(4);Node* o1 = head->left->right = new Node(7);Node* o2 = head->left->left->left = new Node(1);head->left->left->right = new Node(5);head->right->left = new Node(9);head->right->right = new Node(11);cout << lca(head, o1, o2)->value << endl;
}

5.1.5.2方法2

情況1：o1是o2的最低公共祖先（LCA），或o2是o1的最低公共祖先
情況2：o1和o2不互為最低公共祖先（LCA）

Node* lowestAncestor(Node* head, Node* o1, Node* o2)
{if (head == nullptr || head == o1 || head == o2){return head;}Node* left = lowestAncestor(head->left, o1, o2);Node* right = lowestAncestor(head->right, o1, o2);if (left != nullptr && right != nullptr)//左樹右樹上都不為空就返回頭部{return head;}return left != nullptr ? left : right;//兩顆樹并不都有返回值，誰不為空返回誰
}

在一個(gè)4層的完全二叉樹中，o1，o2都在右樹中，代碼會(huì)怎么在左樹中運(yùn)行的狀況

在一個(gè)4層的完全二叉樹中，o1和o2都在右樹中，那么代碼將按照以下方式在左樹中運(yùn)行：

運(yùn)行到第1行，此時(shí)head參數(shù)指向根節(jié)點(diǎn)。

運(yùn)行到第3行，由于head不為空且不等于o1和o2，不會(huì)進(jìn)入if語句，繼續(xù)執(zhí)行下一行。

運(yùn)行到第7行，遞歸調(diào)用lowestAncestor函數(shù)傳入head->left，即根節(jié)點(diǎn)的左子節(jié)點(diǎn)，在左樹中進(jìn)行遞歸。

遞歸調(diào)用的時(shí)候，繼續(xù)從第1行開始執(zhí)行，將左子節(jié)點(diǎn)作為新的head參數(shù)。

運(yùn)行到第3行，由于head不為空且不等于o1和o2，不會(huì)進(jìn)入if語句，繼續(xù)執(zhí)行下一行。

運(yùn)行到第7行，繼續(xù)遞歸調(diào)用lowestAncestor函數(shù)傳入head->left，即左子節(jié)點(diǎn)的左子節(jié)點(diǎn)，在左樹中繼續(xù)遞歸。

重復(fù)步驟4-6，直到遞歸到最底層的葉子節(jié)點(diǎn)。

當(dāng)遞歸到最底層葉子節(jié)點(diǎn)時(shí)，head為nullptr，因此第5行的條件判斷為true，返回nullptr。

返回到上一層遞歸調(diào)用處，繼續(xù)執(zhí)行第6行。

運(yùn)行到第6行，遞歸調(diào)用lowestAncestor函數(shù)傳入head->right，即左子節(jié)點(diǎn)的右子節(jié)點(diǎn)，在左樹中繼續(xù)遞歸。

重復(fù)步驟4-10，直到遞歸到包含o1和o2的子樹。

當(dāng)遞歸到包含o1和o2的子樹時(shí)，第3行的條件判斷為true，返回包含o1和o2的子樹的根節(jié)點(diǎn)。

因此，在這種情況下，代碼將在左樹中執(zhí)行直到找到包含o1和o2的子樹的根節(jié)點(diǎn)，并返回該節(jié)點(diǎn)。

當(dāng)?shù)竭_(dá)最深層時(shí)會(huì)返回到上一層的遞歸調(diào)用處繼續(xù)執(zhí)行下一行代碼。這是遞歸的特性。在這種情況下，當(dāng)遞歸到達(dá)最底層葉子節(jié)點(diǎn)時(shí)，遞歸調(diào)用將返回到上一層遞歸調(diào)用處，繼續(xù)執(zhí)行下一行代碼。

5.1.6例6：在二叉樹中找到一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)

先在有一種新的二叉樹節(jié)點(diǎn)類型如下

public class Node{public int value;public Node left;public Node right;public Node parent;public Node(int val){value=val;}
}

該結(jié)構(gòu)比普通二叉樹節(jié)點(diǎn)結(jié)構(gòu)多了一個(gè)指向父節(jié)點(diǎn)的parent指針
假設(shè)有一棵Node類型的節(jié)點(diǎn)組成的二叉樹，樹中每個(gè)節(jié)點(diǎn)的parent指針都正確地指向自己的父節(jié)點(diǎn)，頭節(jié)點(diǎn)的parent指向null。
只給一個(gè)在二叉樹中的某個(gè)節(jié)點(diǎn)node，請實(shí)現(xiàn)返回node的后繼節(jié)點(diǎn)的函數(shù)

在二叉樹的中序遍歷的序列中， node的下一個(gè)節(jié)點(diǎn)叫作node的后繼節(jié)點(diǎn)。

題意解析：正常來將需要中序排列才能找到后繼節(jié)點(diǎn)，但是此時(shí)的時(shí)間復(fù)雜度為O(N)，當(dāng)題中給出了指向父節(jié)點(diǎn)的指針，那么，如果兩個(gè)節(jié)點(diǎn)之間真實(shí)距離為k的話能不能讓時(shí)間復(fù)雜度變?yōu)镺(k)

情況1：x有右樹的時(shí)候，它的后繼節(jié)點(diǎn)為他的右樹上的最左節(jié)點(diǎn)

情況2：x無右樹的時(shí)候，
看它的父節(jié)點(diǎn)，是不是它的父節(jié)點(diǎn)的左孩子，不是，
看它的父節(jié)點(diǎn)，是不是它的父節(jié)點(diǎn)的左孩子，不是，
看它的父節(jié)點(diǎn)，是不是它的父節(jié)點(diǎn)的左孩子，不是，
看它的父節(jié)點(diǎn)，是不是它的父節(jié)點(diǎn)的左孩子，是，
它的后繼節(jié)點(diǎn)為此節(jié)點(diǎn)的父

因?yàn)閷Υ斯?jié)點(diǎn)來說，x是其左子樹最右的節(jié)點(diǎn)

情況3：沒有后繼，當(dāng)處于整個(gè)二叉樹的最右側(cè)最后一個(gè)節(jié)點(diǎn)是沒有后繼的

#include <iostream>struct Node {int val;Node* left;Node* right;Node* parent;Node (int val):val(val), left(nullptr), right(nullptr),parent(nullptr) {}
};Node* getMostLeftNode(Node* node) {if (node == nullptr) {return node;}while (node->left != nullptr) {node = node->left;}return node;
}Node* getNextNode(Node* node) {if (node == nullptr) {return node;}if (node->right != nullptr) {   // if node has right tree, we find the leftest nodereturn getMostLeftNode(node->right);} else {Node* parent = node->parent;while (parent != nullptr && parent->left != node) {node = parent;parent = node->parent;}return parent;}
}int main()
{Node* head = new Node(6);head->parent = nullptr;head->left = new Node(3);head->left->parent = head;head->left->left = new Node(1);head->left->left->parent = head->left;head->left->left->right = new Node(2);head->left->left->right->parent = head->left->left;head->left->right = new Node(4);head->left->right->parent = head->left;head->left->right->right = new Node(5);head->left->right->right->parent = head->left->right;head->right = new Node(9);head->right->parent = head;head->right->left = new Node(8);head->right->left->parent = head->right;head->right->left->left = new Node(7);head->right->left->left->parent = head->right->left;head->right->right = new Node(10);head->right->right->parent = head->right;Node* test1 = head->left->left;std::cout << test1->val <<  " next node: " <<  getNextNode(test1)->val << std::endl;Node* test2 = head->left->left->right;std::cout << test2->val <<  " next node: " <<  getNextNode(test2)->val << std::endl;Node* test3 = head->right->right;std::cout << test3->val <<  " next node: " <<  getNextNode(test3)<< std::endl;return 0;
}

5.1.7例7：二叉樹的序列化和反序列化

就是內(nèi)存里的一棵樹如何變成字符串形式，又如何從字符串形式變成內(nèi)存里的樹
如何判斷一顆二叉樹是不是另一棵二叉樹的子樹?
由內(nèi)存變?yōu)樽址行蛄谢?#xff0c;由字符串還原為內(nèi)存結(jié)構(gòu)叫反序列化

先序、中序、后序、按層等方式序列化都可以，以先序方式舉例
例：
看圖中左側(cè)樹
_ # _表示為空
來到頭節(jié)點(diǎn)1：1
左孩子為空：1 _ # _
右孩子為1：1 _ # _ 1 _
右->左孩子為1：1 _ # _ 1 _ 1 _
右->左->左孩子為空：1 _ # _ 1 _ 1 _ # _
右->左->右孩子為空：1 _ # _ 1 _ 1 _ # _ # _
右->右孩子為空：1 _ # _ 1 _ 1 _ # _ # _ # _

看圖中右側(cè)樹
來到頭節(jié)點(diǎn)1：1
左孩子為1：1 _ 1 _
左->左孩子為空：1 _ 1 _ # _
左->右孩子為1：1 _ 1 _ # _ 1 _
左->右->左孩子為1：1 _ 1 _ # _ 1 _ # _
左->右->右孩子為1：1 _ 1 _ # _ 1 _ # _ # _
右孩子為空：1 _ 1 _ # _ 1 _ # _ # _ # _

以符號(hào)還原可以還原
1，#，1，1，#，#，#，
根據(jù)先序遍歷
先1為頭：#，1，1，#，#，#，
左孩子為空：1，1，#，#，#，
右孩子為1：1，#，#，#，
右->左孩子為1：#，#，#，
右->左->左孩子為空：#，#，
右->左->右孩子為空：#，
右->右孩子為空：

前序遍歷序列化代碼

前序遍歷反序列化代碼

5.1.8例8：折紙問題

請把一段紙條豎著放在桌子上，然后從紙條的下邊向上方對折1次，壓出折痕后展開。
此時(shí)折痕是凹下去的，即折痕突起的方向指向紙條的背面。
如果從紙條的下邊向上方連續(xù)對折2次，壓出折痕后展開，此時(shí)有三條折痕，從上到下依次是下折痕、下折痕和上折痕。
給定一個(gè)輸入?yún)?shù)N，代表紙條都從下邊向上方連續(xù)對折N次。請從上到下打印所有折痕的方向。
例如:N=1時(shí)，打印:down N=2時(shí)，打印:down down up

折紙發(fā)現(xiàn)，會(huì)在折痕上方出現(xiàn)凹折痕，在下方出現(xiàn)凸折痕


只用了N個(gè)空間