数据结构与算法篇(三)二叉树
1. 二叉树
二叉树是一种非线性结构，通常采用链式存储结构，存储节点由数据域和指针域（指针域分为左指针和右指针）组成。
用C++表示如下：
// 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){}};
二叉树有如下性质：
二叉树的第K层上，至多有2^(k-1)个节点，例如k=1时，只有一个节点——根节点；
深度为k的二叉树至多有2^k-1个节点，例如k=2时，节点数为3；
具有n个节点的完全二叉树的深度至少为[log2n]+1；
有n个节点的完全二叉树各节点如果用顺序方式存储：
left=index*2+1;
rignt=index*2+2;
序数>=floor(n/2)都是叶子节点；
1.1. 二叉树的种类
完全二叉树
定义：除最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干结点的二叉树。
满二叉树
定义：一个深度为k且有2^k-1个节点的二叉树称为满二叉树；满二叉树所有的叶子节点都有同样的深度；
满二叉树是一种完全二叉树，但完全二叉树不一定是满二叉树。
二叉堆
二叉堆是一种完全二叉树，其父节点的键值总是大于(小于)或等于任何一个子节点的键值。
最大堆：父节点的键值大于或等于任何一个子节点的键值；
最小堆：父节点的键值小于或等于任何一个子节点的键值。
二叉搜索树（二叉查找树，二叉排序树）
二叉搜索树，是一种有序二叉树，其性质为：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
没有键值相等的节点。
对二叉搜索树进行中序遍历，即可得到有序的数列；二叉查找树的高度决定了查找的效率。
堆是为了实现排序而设计的一种数据结构，在堆中查找一个结点需要进行遍历，其平均时间复杂度是O(n)。
二叉排序树是为了实现动态查找而设计的数据结构，它是面向查找操作的。对于目标节点的查找过程类似于有序数组的二分查找，在二叉排序树中查找一个结点的平均时间复杂度是O(logn)；
平衡二叉树（AVL树）
平衡二叉树左右两个子树高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。即：平衡二叉树的深度=max(左子树的深度，右子树的深度)+1；如下图：
平衡二叉树的作用：避免二叉查找树退化为单链表的极端情况，保证查找，插入，删除的时间复杂度为O(log n)。
另有平衡二叉树之AVL树，红黑树，B树，B+树等，会单独拎出章节讲解
1.2. 二叉树的遍历
1. 二叉树的深度优先遍历
前序遍历（根左右）：
先访问根节点
前序遍历左子树
前序遍历右子树中序遍历（左根右）：
先中序遍历左子树
然后访问根节点
再中序遍历右子树后序遍历（左右根）：
先后续遍历左子树
再后续遍历右子树
最后访问根节点
2. 二叉树深度优先遍历的两种方法
1. 递归法
递归法三要素：
确定递归函数的参数和返回值
确定终止条件
确定单层递归的逻辑
根据上述三要素，以前序遍历为例：
(1) 确定递归函数的参数和返回值：遍历二叉树，并且输出二叉树的遍历结果，输入参数应为二叉树及结果数组，返回为voidvoid traversal(TreeNode* root, vector<int>& vec)
(2) 确定终止条件：当前输入的二叉树节点为NULL时，该子树已遍历完，则终止递归if(root==nullptr) return;
(3) 确定单层递归的逻辑：前序遍历是根左右的逻辑，所以单层递归首先要取根节点的值，再遍历左子树，右子树vec.push_back(root->val); traversal(root->left,vec); traversal(root->right,vec);
则前序遍历的代码整理如下(leetcode 144题)：
void traversal(TreeNode* root, vector<int>& vec){f(root==nullptr) return;vec.push_back(root->val);traversal(root->left,vec);traversal(root->right,vec);}
同理，中序遍历(leetcode 94)：
void traversal(TreeNode* root, vector<int>& vec){f(root==nullptr) return;traversal(root->left,vec);vec.push_back(root->val);traversal(root->right,vec);}
后续遍历(leetcode 145题)：
void traversal(TreeNode* root, vector<int>& vec){f(root==nullptr) return;traversal(root->left,vec);traversal(root->right,vec);vec.push_back(root->val);}
2. 迭代法
递归法用的是系统栈，通过出栈入栈，实现二叉树的遍历。迭代法，通过stack模拟系统栈，通过入栈出栈实现二叉树的遍历。
前序遍历：
首先我们应该创建一个stack用来存放节点，首先我们想要打印根节点的数据，此时stack里面的内容为空，所以我们优先将头结点加入stack，然后打印。
之后我们应该先打印左子树，然后右子树。所以先加入stack的就是右子树，然后左子树。(栈的先入后出特性)
/*** 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<int> preorderTraversal(TreeNode* root) {vector<int> res;if(root){stack<TreeNode*> tmp;tmp.push(root);while(!tmp.empty()){TreeNode* node=tmp.top();tmp.pop();res.push_back(node->val);if(node->right) tmp.push(node->right);if(node->left) tmp.push(node->left);}}return res;}};
中序遍历：
中序遍历是左根右的遍历次序，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中）,代码如下：
/*** 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<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> tmp;while(root||!tmp.empty()){while(root){tmp.push(root); //访问左子树到最底层root=root->left;//左}TreeNode* node=tmp.top();tmp.pop();res.push_back(node->val);//根if(node){root=node->right; //再访问右子树}}return res;}};
后序遍历：
前序遍历的次序为 根->左->右，
后序遍历的次序为 左->右->根，
只需将前序遍历的代码调整为 根->右->左 的访问顺序，并逆序输出遍历的数组结果，即可得到 左->右->根 的次序。代码如下：
/*** 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<int> postorderTraversal(TreeNode* root) {vector<int> res;if(root){stack<TreeNode*> tmp;tmp.push(root);while(!tmp.empty()){TreeNode* node=tmp.top();tmp.pop();res.push_back(node->val);if(node->left) tmp.push(node->left);if(node->right) tmp.push(node->right);}reverse(res.begin(),res.end());}return res;}};
3. 二叉树的广度优先遍历
二叉树的广度优先遍历，即层序遍历，是逐层的遍历二叉树的节点。需要用队列来辅助。
如图所示：将根节点放入队列中
首先根节点出队，如果其左右子树不为空，则入队
然后拿出第二层的节点，并根据其左右子树是否为空，将左右子树继续依次放入队列
每次遍历的值放入结果集中，得到最终的层序遍历结果。
废话不多说，上代码：
迭代法：
/*** 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) {queue<TreeNode*> q;vector<vector<int>> res;q.push(root);while(root&&!q.empty()){int n=q.size();vector<int> tmp;for(int i=0;i<n;i++){TreeNode* node=q.front();q.pop();tmp.push_back(node->val);if(node->left) q.push(node->left);if(node->right) q.push(node->right);}res.push_back(tmp);}return res;}};
递归法：
因为每层的节点值要分开记录，所以递归的参数除了节点node以外还需要当前层数level
如果节点已为空，return，结束当前递归分支即可
如果res的长度已经和当前层数level相等，说明res需要多加个位置了，因为level是res数组的索引，索引是一定比长度要小的，如果相等说明数组长度不够长了，得扩容
把当前节点加到对应层的数组中去
继续依次遍历左右字节点，层数level + 1
/*** 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) {vector<vector<int>> res;bfs(root,res,0);return res;}void bfs(TreeNode* root, vector<vector<int>> &res, int lev){if(!root) return;if(lev>=res.size()){res.push_back(vector<int>());}res[lev].push_back(root->val);if(root->left) bfs(root->left,res,lev+1);if(root->right) bfs(root->right,res,lev+1);}};
2. 重构二叉树
遍历二叉树，可得到相应的节点数组。那么给出遍历的数组，是否能够还原二叉树呢？答案是肯定的。还原一颗普通的二叉树，仅靠某一种遍历序列是不行的，一般需要两种遍历数组。
2.1 前序遍历和中序遍历，还原二叉树
在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。
例如下面这棵二叉树：
1\2 3\ / \4 5 6 7
前序遍历的结果是: [1,2,4,5,3,6,7]
中序遍历的结果是: [4,2,5,1,6,3,7]
推导思路：前序遍历的第一个元素为根节点，根据第一个元素，扫描中序遍历序列，确定其在中序遍历序列的位置，位置左面为左子树，右侧为右子树。以此类推，通过递归，可得代码如下：
递归法：
/*** 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) {unordered_map<int,int> mp;// 构造哈希映射，帮助我们快速定位根节点int n=preorder.size();for(int i=0;i<n;i++){mp[inorder[i]]=i;}return dfs(preorder,inorder,0,n-1,0,n-1,mp);}TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pStart, int pEnd, int iStart, int iEnd, unordered_map<int,int>& mp){if(pStart>pEnd) return nullptr;// 前序遍历中的第一个节点就是根节点// 在中序遍历中定位根节点int ioRoot=mp[preorder[pStart]];// 得到左子树中的节点数目int subTreeLeft=ioRoot-iStart;// 先把根节点建立出来TreeNode* root=new TreeNode(preorder[pStart]);// 递归地构造左子树，并连接到根节点// 先序遍历中:从 左边界+1 开始的 subTreeLeft 个元素就对应了中序遍历中:从 左边界 开始到 根节点定位-1 的元素root->left=dfs(preorder,inorder,pStart+1,pStart+subTreeLeft,iStart,iStart+subTreeLeft,mp);// 递归地构造右子树，并连接到根节点// 先序遍历中:从 左边界+1+左子树节点数目 开始到 右边界 的元素就对应了中序遍历中:从 根节点定位+1 到 右边界 的元素root->right=dfs(preorder,inorder,pStart+subTreeLeft+1,pEnd,iStart+subTreeLeft+1,iEnd,mp);return root;}};
迭代法
我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针index指向中序遍历的第一个节点；
我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的左子树,入栈；如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向右移动 index，直到当前节点值与栈顶值不同时，为右子树，压入栈；
代码如下：
/*** 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) {if(preorder.size()==0) return nullptr;TreeNode* root=new TreeNode(preorder[0]);stack<TreeNode*> stk;stk.push(root);int inorderndex(0);for(int i=1;i<preorder.size();i++){TreeNode* node=stk.top();int prVal=preorder[i];if(node->val!=inorder[inorderndex]){node->left=new TreeNode(prVal);stk.push(node->left);}else{while(!stk.empty()&&stk.top()->val==inorder[inorderndex]){node=stk.top();stk.pop();inorderndex++;}node->right=new TreeNode(prVal);stk.push(node->right);}}return root;}};
2.2 后续遍历和中序遍历，还原二叉树
中序遍历序列 和 后序遍历序列 根据这两种遍历的特性我们可以得出两个结论:
在后序遍历序列中,最后一个元素为树的根节点
在中序遍历序列中,根节点的左边为左子树，根节点的右边为右子树
根据中序遍历和后续遍历的特性我们进行树的还原过程分析
首先在后序遍历序列中找到根节点(最后一个元素)
根据根节点在中序遍历序列中找到根节点的位置
根据根节点的位置将中序遍历序列分为左子树和右子树
根据根节点的位置确定左子树和右子树在中序数组和后续数组中的左右边界位置
递归构造左子树和右子树
返回根节点结束
需要定义几个变量帮助我们进行树的还原
HashMap 需要一个哈希表来保存中序遍历序列中,元素和索引的位置关系.因为从后序序列中拿到根节点后，要在中序序列中查找对应的位置,从而将数组分为左子树和右子树
int ri 根节点在中序遍历数组中的索引位置
中序遍历数组的两个位置标记 [is, ie]，is 是起始位置，ie 是结束位置
后序遍历数组的两个位置标记 [ps, pe] ps 是起始位置，pe 是结束位置
/*** 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>& inorder, vector<int>& postorder) {// 构造哈希映射，帮助我们快速定位根节点unordered_map<int,int> mp;int n=postorder.size();for(int i=0;i<n;i++){mp[inorder[i]]=i;}return dfs(inorder,postorder,0,n-1,0,n-1,mp);}TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int pStart, int pEnd, int iStart, int iEnd, unordered_map<int,int>& mp){if(pStart>pEnd) return nullptr;int rootVal=postorder[pEnd];//定位根节点在中序数组中的位置int inorderex=mp[rootVal]//得到左子树的节点数目int subTreeNum=inorderex-iStart;//建立根节点TreeNode* root=new TreeNode(rootVal);// 递归地构造左子树，并连接到根节点// 后序遍历中:从 左边界 开始的 subTreeNum-1 个元素就对应了中序遍历中:从 左边界 开始到 根节点定位-1 的元素root->left=dfs(inorder,postorder,pStart,pStart+subTreeNum-1,iStart,inorderex-1,mp);// 后序遍历中:从 左边界+subTreeNum 开始到末尾-1 个元素就对应了中序遍历中:从 根节点+1 开始到 末尾 的元素root->right=dfs(inorder,postorder,pStart+subTreeNum,pEnd-1,inorderex+1,iEnd,mp);return root;}};
迭代法：
我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（后序遍历的最后一个节点），指针index指向中序遍历的最后一个节点；
我们依次枚举后序遍历中除了最后一个节点以外的每个节点。如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的右子树,入栈；如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向左移动 index，直到当前节点值与栈顶值不同时，为左子树，压入栈；
代码如下：
/*** 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>& inorder, vector<int>& postorder) {if(postorder.size()==0) return nullptr;int n=postorder.size();TreeNode* root=new TreeNode(postorder[n-1]);stack<TreeNode*> stk;stk.push(root);int inorderIndex(n-1);for(int i=n-2;i>=0;i--){TreeNode* node=stk.top();int postVal=postorder[i];if(node->val!=inorder[inorderIndex]){node->right=new TreeNode(postVal);stk.push(node->right);}else{while(!stk.empty()&&stk.top()->val==inorder[inorderIndex]){node=stk.top();stk.pop();inorderIndex--;}node->left=new TreeNode(postVal);stk.push(node->left);}}return root;}};
3. 二叉搜索树
二叉搜索树，又可以叫二叉排序树。它具有以下性质：
如果节点的左子树不空，则左子树上所有结点的值均小于等于它的根结点的值；
如果节点的右子树不空，则右子树上所有结点的值均大于等于它的根结点的值；
任意节点的左、右子树也分别为二叉搜索树；
二叉搜索树支持许多动态集合操作，包括SEARCH（查找指定结点）、MINIMUM（最小关键字结点）、MAXMUM（最大关键字结点）、PREDECESSOR（结点的先驱）、SUCCESSOR（结点的后继）、INSERT（结点的插入）和DELETE（结点的删除）等。因此，我们使用一棵搜索树既可以作为一个字典又可以作为一个优先队列。
接下来讲一下二叉搜索树的一些操作
3.1 二叉搜索树的中序遍历
根据二叉搜索树的性质，通过中序遍历，可以得到有序的二叉搜索树。在验证二叉搜索树一题中，可以用递归和迭代两种方法实现：
中序遍历递归法：
/*** 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:long pre=(long)INT_MIN-1;bool isValidBST(TreeNode* root) {if(root==nullptr) return true;if(!isValidBST(root->left)){return false;}if(root->val<=pre){return false;}pre=root->val;if(!isValidBST(root->right)){return false;}return true;}};
中序遍历迭代法：
/*** 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:bool isValidBST(TreeNode* root) {if(root==nullptr) return true;stack<TreeNode*> s;long long pre=(long long)INT_MIN-1;while(root||!s.empty()){while(root){s.push(root);root=root->left;}TreeNode* node=s.top();s.pop();if(node->val<=pre){return false;}pre=node->val;if(node) root=node->right;}return true;}};
3.2 二叉搜索树的后续遍历
leetcode中的一道题，二叉搜索树的后续遍历序列：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
二叉搜索树的特点是左子树的值<根节点<右子树的值。而后续遍历的顺序是：左子节点→右子节点→根节点；比如下面这棵二叉树，他的后续遍历是
[3，5，4，10，12，9]
该题涉及到两个性质：
对于一棵二叉树，根据后续遍历左右根，得到的数组最后的元素是根节点（同理前序遍历的首位元素是根节点），因此9是该二叉树的根节点。
二叉搜索树左子树的值<根节点<右子树的值，可以按照分治的思路，从前往后遍历数组，找到第一个比9大的数字10，那么10后面的[10，12]（除了9）都是9的右子节点，10前面的[3，5，4]都是9的左子节点，后面的需要判断一下，如果有小于9的，说明不是二叉搜索树，直接返回false。然后再以递归的方式判断左右子树。
代码如下：
class Solution {public:bool verifyPostorder(vector<int>& postorder) {return devideOrder(postorder,0,postorder.size()-1);}bool devideOrder(vector<int>& postorder, int left, int right){if(left>=right) return true;int mid=left;while(postorder[mid]<postorder[right]){mid++;}int i=mid;while(i<right){if(postorder[i]<postorder[right]){return false;}i++;}return devideOrder(postorder,mid,right-1)&&devideOrder(postorder,left,mid-1);}};
另外关于二叉搜索树的操作，可看leetcode的几道题：
二叉搜索树与双向链表 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
二叉搜索树的最近公共祖先 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
二叉搜索树的第k大节点 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/