学习二叉树有一个很重要的思想就是分治（将一个大问题划分为最小规模的子问题），常用方法之一就是递归，而递归是很抽象的，当对递归过程不理解时，建议多画图将递归过程实例化，拒绝人脑压栈

文章目录

• 根据二叉树创建字符串
• 二叉树层序遍历（变形一）
• 二叉树层序遍历（变形二）
• 二叉树的最近公共祖先（LCA）
• 二叉搜索树转排序双向链表
• 中序+前序构造二叉树
• 中序+后序构造二叉树
• 前序非递归实现
• 中序非递归实现
• 后序非递归实现

根据二叉树创建字符串

原题：根据二叉树创建字符串
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

大致框架

** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    string tree2str(TreeNode* root);};

先考虑可以省略括号的情况：

1. 节点的right为空
2. 节点的left和right都为空

不能省略括号就和以上情况相反

1. 节点的right不为空
2. 节点的left不为空或right不为空

class Solution {public://通过子函数完成字符串创建    void _tree2str(TreeNode* root, string& str)    { if (root == nullptr)     return;  //跟不需要括起来，直接插入 str+=to_string(root->val); if (root->left || root->right) {     str+='(';     _tree2str(root->left, str);     str+=')'; } if (root->right) {     str+='(';     _tree2str(root->right, str);     str+=')'; }    }    string tree2str(TreeNode* root) { string str; _tree2str(root, str); return str;    }};

二叉树层序遍历（变形一）

原题：二叉树层序遍历
给你二叉树的根节点 root ，返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）

大致框架

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector<vector<int>> levelOrder(TreeNode* root);};

这道题就是层序遍历的变形，先来回顾一下层序遍历是如何实现的

void LevelOrder(TreeNode* root){if (root == nullptr)return;queue<TreeNode*> q;q.push(root);while (!q.empty()){TreeNode* front = q.front();cout << front->val << " ";//孩子进队列if (front->left)q.push(front->left);if (front->right)q.push(front->right);//父亲出队列q.pop();}cout<<endl;}

上面不需要记录每层的节点个数，直接输出到控制台或是数组中即可，但这道题需要记录每层节点的个数，每层放在一个一维数组中，然后返回二维数组。所以我们只需要定义一个LevelSize记录每层的节点个数即可

class Solution {public:    vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; if (root)     q.push(root); int LevelSize=1;//第一层只有一个根节点，所以初始化为1 vector<vector<int>> vv; while (!q.empty()) { vector<int> v;//根据LevelSize的大小确定每一层的节点个数     while (LevelSize--)     {  TreeNode* front = q.front();  //pop之前将队头插入vector，再让它的左右孩子入队列  v.push_back(front->val);  if (front->left)      q.push(front->left);  if (front->right)      q.push(front->right);  q.pop();     }     //一层遍历完后，插入到二维数组中     vv.push_back(v);     //更新下一层节点个数     LevelSize=q.size(); } return vv;    }};

二叉树层序遍历（变形二）

原题：二叉树层序遍历ii
搞懂上面的层序遍历，这道题就非常简单了，题目说要倒着遍历，所以只需要正常遍历，最后reverse即可

class Solution {public:    vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> vv; queue<TreeNode*> q; if (root) {     q.push(root); } int LevelSize=1; while (!q.empty()) { vector<int> v;     while (LevelSize--)     {  TreeNode* front=q.front();  //孩子进队列  if (front->left)      q.push(front->left);  if (front->right)      q.push(front->right);  //父亲出队列  v.push_back(front->val);  q.pop();     }     vv.push_back(v);     LevelSize=q.size(); } reverse(vv.begin(), vv.end());return vv;     }};

二叉树的最近公共祖先（LCA）

原题：二叉树最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

大致框架

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    bool Find(TreeNode* root, TreeNode* node); };

通过画图可以发现，p，q的最近公共祖先就是两者到根节点路径上的交点，最近公共祖先有以下特征：

1. 当一个节点的左子树出现节点p，右子树出现节点q，或左子树出现节点q，右子树出现节点p，那么该节点就是p，q的公共祖先
2. 当然也有可能p，q的公共祖先就是p，q其中之一
   

这题如果是搜索二叉树就很简单了

class Solution {public:     int lowestCommonAncestor(TreeNode* root, int p, int q) { if (root == nullptr)     return -1;  //一个在左一个在右，或者祖先是自己，就找到了 if ((root->val>=p && root->val<=q)||(root->val<=p&&root->val>=q))     return root->val;  //都在左树，进左树找 else if (root->val > p && root->val > q)     return lowestCommonAncestor(root->left, p, q); else //都在右树，进右树找     return lowestCommonAncestor(root->right, p, q);    } };

再回到本题中来
思路一：暴力破解，逐个查找，时间复杂度O(N²)

class Solution {public://查找root的子树是否存在node    bool Find(TreeNode* root, TreeNode* node)    { if (root == nullptr)     return false; if (root == node)     return true; return Find(root->left, node) || Find(root->right, node);    }    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr || root == p || root == q)     return root; //通过4个bool值，判断p，q在root的左子树还是右子树 bool pInLeft, pInRight, qInLeft, qInRight; pInLeft = Find(root->left, p);//p在左子树，就不会再右子树，反之 pInRight=!pInLeft; qInLeft = Find(root->left, q);//同理q qInRight = !qInLeft; //如果都在当前节点的左树，就往左子树找 if (pInLeft && qInLeft)     return lowestCommonAncestor(root->left, p, q);  //同理 else if (pInRight && qInRight)     return lowestCommonAncestor(root->right, p, q); //一个在左子树，一个在右子树直接往回返 else if ((pInLeft && qInRight) || (pInRight &&qInLeft))     return root; else return nullptr;    }};

思路二：时间复杂度O(N)

• 采用后序遍历的思想，自底向顶回溯，p，q找到后不断往回返，回溯到公共祖先

class Solution {public:    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { //走到空，或当前根为p或q就返回根 if (root == nullptr || root == p || root == q)     return root; //查找左子树是否存在p或q TreeNode* isLeft=lowestCommonAncestor(root->left, p, q); //查找右子树是否存在p或q TreeNode* isRight=lowestCommonAncestor(root->right, p, q); //如果当前节点的左右子树一个包含p，一个包含q，说明该节点是最近公共祖先 if (isLeft && isRight)     return root; //如果左子树不为空，说明p，q其中之一在该节点的左子树，直接往回返 else if (isLeft)     return isLeft; //右子树不为空，，说明p，q其中之一在该节点的右子树上，继续往回返 else if (isRight)     return isRight; else //都找不到就返回nullptr     return nullptr;    }};

思路三：时间复杂度O(N)
如果这是一个三叉链的结构，就个指向父亲的指针就非常简单了，就是链表相交的问题。通过p，q两节点到根节点的路径，找到路径相交点，也就是p，q的公共祖先，采用先序思想，我们可以通过两个栈模拟实现，栈Pathq实现q到根节点的路径，栈Pathp实现p到根节点的路径
以p->value=6，q->value=7为例，公共祖先就是5
基本思想，以栈Pathq为例：

1. 只要节点不为空，直接往栈里push
2. 判断该节点的左右子树是否包含存在q
3. 如果左右子树都不存在q就pop掉，再return false

class Solution {public:    bool SearchPath(TreeNode* root, TreeNode* node, stack<TreeNode*>& st)    { if (root == nullptr)     return false; st.push(root);//先入栈再判断 if (root == node)     return true; //在左树 if (SearchPath(root->left, node, st))     return true; //在右树 if (SearchPath(root->right, node, st))     return true; //左右都没有找到，证明不在当前子树中，pop掉 st.pop(); return false;    }    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr || root == p || root == q)     return root; stack<TreeNode*> Pathp, Pathq; SearchPath(root, p, Pathp); SearchPath(root, q, Pathq); while (Pathp.size() != Pathq.size()) {     if (Pathp.size() > Pathq.size())  Pathp.pop();     else   Pathq.pop(); } //长度相等时，找到相交路径 while (Pathp.top() != Pathq.top()) {     Pathp.pop();     Pathq.pop(); } //返回其中一个即可 return Pathp.top();    }};

二叉搜索树转排序双向链表

原题：二叉树与中序链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

大致框架

/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}};*/class Solution {public:TreeNode* Convert(TreeNode* pRootOfTree);};

对搜索二叉树不了解的可以看这篇文章：二叉搜索树以及K模型与KV模型
首先分析题目要求：

1. 要排升序
2. 将节点的left当做双链表的prev指向前一个节点
3. 将节点的right当做双链表的next指向下一个节点

而二叉搜索树中序遍历就可以排升序，所以只需要在中序递归遍历过程中更改节点的链接关系即可。定义一个prev初始化为nullptr，这样就可以让当前根节点（定义为cur），cur->left指向prev，那如何让cur->right指向下一个节点呢？以下图为例
下一个节点肯定是无法预料到的，就像我们不知道明天会发生什么，但我们知道昨天发生了什么啊，所以可以让prev->right指向cur
ps：递归prev肯定要传引用，因为prev每次都要发生变化，每次递归调用之前让prev走到cur的位置，同时需要判断prev是否为空

class Solution {public:    //中序转换    void InOrderConvert(TreeNode* cur, TreeNode*& prev)    { if (cur == nullptr)     return; //左 InOrderConvert(cur->left, prev); //根:访问的节点依次为4 6 8 10 12 14 16 cur->left=prev; if (prev)     prev->right=cur; prev=cur; //右 InOrderConvert(cur->right, prev);    }    TreeNode* Convert(TreeNode* pRootOfTree) { if (pRootOfTree == nullptr)     return nullptr; TreeNode* prev=nullptr; InOrderConvert(pRootOfTree, prev);  //找到链表的头 TreeNode* head = pRootOfTree; while (head->left) {     head=head->left; }  return head;    }};

中序+前序构造二叉树

原题：中序+前序构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
大致框架

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder);};

当中序和前序数组中无重复元素时，那我们就可以根据这两个数组建树

1. 根据前序可以确定根
2. 确定根后，可以将中序数组划分为左子树   根   右子树

以示例一为例

class Solution {public:    TreeNode* _bulidTree(vector<int>& preorder, vector<int>& inorder, int& index    , int inbegin, int inend)    {   // 区间不存在时，返回空 if (inbegin > inend)     return nullptr; //根 TreeNode* root=new TreeNode(preorder[index]); //确定左子树  根 右子树 int rooti=inbegin;//找到根在inorder中的位置 while (inorder[rooti] != preorder[index]) {     ++rooti; } ++index;//往后走 //确定区间[inbegin, rooti-1] rooti  [rooti+1, inend] root->left=_bulidTree(preorder,inorder,index,inbegin,rooti-1); root->right=_bulidTree(preorder,inorder,index,rooti+1,inend); return root;    }    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int index=0;//preorder下标从0开始,传引用 return _bulidTree(preorder, inorder, index, 0, inorder.size()-1);    }};

当然如果搞一个hash表存中序数组的元素和对应下标可以减少查找

中序+后序构造二叉树

原题：中序+后序构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

这道题和上面的类似，是通过中序和后序建树的，后序遍历顺序为：左子树->右子树->根，所以需要从右往前确定根然后再确定右子树的根

class Solution {public:     TreeNode* _bulidTree(vector<int>& inorder, vector<int>& postorder, int& posti , int inbegin, int inend)    { if (inbegin > inend)     return nullptr; //根 TreeNode* root=new TreeNode(postorder[posti]); //确定左子树  根 右子树 int rooti=inbegin;  while (inorder[rooti] != postorder[posti]) {     ++rooti; } --posti;//往前走 //确定区间[inbegin, rooti-1] rooti  [rooti+1, inend] root->right=_bulidTree(inorder,postorder, posti, rooti+1,inend); root->left=_bulidTree(inorder,postorder, posti,inbegin,rooti-1); return root;    }    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int posti=postorder.size()-1;//postorder下标从最后开始 return _bulidTree(inorder, postorder, posti, 0, inorder.size()-1);    }   };

所以中序+前序和后序其中之一就可以建树，如果是前序+后序是无法构造的，因为无法区分树的左右子树
ps：当然如果给定数组有标识符表示空节点，那么前后序其中之一就可以建树

前序非递归实现

原题：前序遍历

先来回顾一下前序遍历的顺序：先访问根 ，再访问左子树，最后访问右子树。
一颗不为空的树除了可以划分为跟，左子树，右子树外，还可以划分为左路节点+左路节点的右子树。
具体步骤：

1. 依次访问左路节点3 9 15，然后再从后往前依次访问左路节点的右子树，所以可以用一个栈模拟实现，边访问左路节点变压栈
2. 那如何访问左路节点的右子树呢？以子问题的形式访问右子树，如何访问左路节点的就如何访问右子树

class Solution {public:    vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* cur = root; //cur不为空说明还有节点没有push入栈 //栈不为空说明还有节点的右子树没有访问 while (cur || !st.empty()) {     //左路节点入栈     while (cur)     {     v.push_back(top->val);  st.push(cur);  cur=cur->left;     }     TreeNode* top = st.top();  st.pop();     //以子问题的形式访问右子树，如何访问左路节点就如何访问右子树     cur=top->right; } return v;    }};

中序非递归实现

原题：中序遍历

中序遍历顺序：先访问左子树，再访问根，最后访问右子树，和前序非递归类似

class Solution {public:    vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* cur = root; while (cur || !st.empty()) {     //左路节点入栈     while (cur)     {  st.push(cur);  cur=cur->left;     }     TreeNode* top = st.top();     v.push_back(top->val);     st.pop();     //以子问题的形式访问右子树，如何访问左路节点就如何访问右子树     cur=top->right; } return v;    }};

后序非递归实现

原题：后序遍历
前中后序遍历的不同点就是访问根节点的时机不同，而前中序都有一个特点，都是最后访问右子树，而我们把左路节点压栈后，很容易就可以实现最后访问右子树。
而后序遍历需要先访问左子树，再访问右子树，最后访问根。也就是说需要先访问完右子树才能访问根，以下图为例，访问完15后还不能访问9需要先访问9的右子树7才能访问9
ps：这里因为9的右子树只有一个7,而7的左右子树都为空，实际上是最后访问完7再访问的9，那就可以定义一个prev初始化为nullptr，每访问一个节点就记录这个节点，所以当栈顶的top为9时且prev为7时证明已经访问过7了也就是右子树，就可以访问根9了

class Solution {public:    vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* prev = nullptr; TreeNode* cur = root; while (cur || !st.empty()) {     //左路节点入栈     while (cur)     {  st.push(cur);  cur=cur->left;     }     TreeNode* top = st.top();     //当右树为空或右树已经访问完了就可以访问根     if (top->right == nullptr || top->right == prev)     {  v.push_back(top->val);  st.pop();  //记录访问的节点  prev=top;     }      //以子问题的形式访问右子树，如何访问左路节点就如何访问右子树     else  cur=top->right; } return v;    }};