一.方法介绍
- 二叉树的层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列，而先、中、后序遍历则需要用到栈。因此，先、中、后序遍历可以用递归方式实现（通过个别示例来显示进栈出栈的访问顺序），而层序遍历则没有递归方式
一般来说，对于二叉树的递归实现，都要借助于辅助函数来完成
对于树的递归，可以先假设树没有节点、有一个节点、有两个节点、有三个节点的情况去写递归，这样写比较好。
//二叉树的层序遍历queue<TreeNode*> q;q.push(root);while (!q.empty()){int size = q.size();while (size--){TreeNode* temp = q.front();q.pop();if (temp->right) q.push(temp->right);if (temp->left) q.push(temp->left);}}
二叉查找树(BST)
定义
一种特殊的二叉树：它或者是一棵空树，或者是具有下列性质的二叉树，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
查找-在O(logn)时间内
对于一个二叉查找树，可以在O(nlogn)的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值则往左下走，若当前节点的值小于查找值则往右下走。
BST的中序遍历
二叉搜索树的中序遍历是一个单调递增的有序序列。如果我们反序地中序遍历该二叉搜索树，即可得到一个单调递减的有序序列。
BST的插入
从根节点开始，遇到节点值比插入值大的，则向左，遇到节点值比插入值小的，则向右，一直到尾端，即为插入点，作为叶子节点插入。
BST的节点移除
1.若要移除的节点A没有子节点，则直接将A删除，并且将A的父节点的对应位置置为null即可；
2.若要移除的节点A只有一个子节点，则直接将A的子节点连接至A的父节点的对应位置，并删除A节点；（1,2类情况可以归为一类）
3.若要移除的节点A有两个子节点，则以A节点的右子树的最小节点B取代A。（最小节点B即从右子节点开始，一直向左走到底即是），这里可以把B的值和A的值相交换，然后正常删除已经被替换掉值的B节点即可，又归为第1或第2种情况利用遍历结果还原树的结构
只有知道了(先序遍历+中序遍历)或(中序遍历+后序遍历)可以还原树。
- 由先序或者后序确定当前根节点，由中序得到当前根节点的左右子树，然后利用得到的左右子树各自的节点数来划分先序或者后序左右子树的开始（比如先序的左子树的序列的根节点就是当前根节点的下标+1，），然后再进行递归建立。
已知（中序遍历+后序遍历）
https://blog.csdn.net/fanny_git/article/details/78060675
基本思路是：
- 后序遍历的最后一个节点是根节点，
- 然后在中序遍历中找到这个根节点，在这个根节点的左右两侧则是以其为根节点的左右子树的分支。
- 根据分开后的左右子树，在后序遍历序列和中序序列中获得相对应的后序和中序，转到1，直到当前根节点下的子节点都被确定下来即可。
深度优先广度优先
105.从前序与中序遍历序列构造二叉树
- 有一点需要注意的是，递归到下一层时的先序序列需要一个参数标注序列根节点（也即当前序列的开始）
TreeNode* Helper (vector<int>& preorder,int rooti,int start,int end,vector<int>& inorder) {if (start==end){TreeNode*ptr=new TreeNode(inorder[start]);return ptr;}if(start>end)return nullptr;int pviot,i;for (i=start;i<=end;i++){pviot=(inorder[i]==preorder[rooti])? i: pviot;}TreeNode* cur=new TreeNode(inorder[pviot]);cur->left=Helper(preorder,rooti+1,start,pviot-1,inorder);cur->right=Helper(preorder,rooti+pviot-start+1,pviot+1,end,inorder);return cur;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return Helper(preorder,0,0,preorder.size()-1,inorder);}
104.二叉树的最大深度
题目链接
给定一个二叉树，找出其最大深度
解法一: 深度优先搜索-递归法 如果我们知道了左子树和右子树的最大深度l和r，那么该二叉树的最大深度即为max(l,r) + 1 递归边界条件是当递归到空时，返回0。
解法二: 广度优先搜索: -队列模拟法 相当于层序遍历，再加上记录每一层的结点数，一层层遍历，并记录层数。
111.二叉树的最小深度
题目链接
给定一个二叉树，找出其最小深度
解法一：采用层序遍历法，每层遇到叶子结点时，直接返回，即可得到最小深度
解法二：采用递归法 这题和之前的求二叉树的最大深度不太一样 对于[2,null,3,null,4,null,5,null,6,null]这种情况，很容易会陷入2->null这个实际不存在的子树深度=1，但是真正的唯一子树是2->3->4->5->6，唯一深度为5。 因此，需要把结点的某一个子结点为空，另一个子节点存在这种情况，把子节点为空的直接给舍弃掉. 边界条件: root==nullptr时返回0
root->left==nullptr&&root->right==nullptr返回1，表示已经到了叶子结点了
递归：
root->left==nullptr&&root->right!=nullptr时，递归root->right并+1
root->left!=nullptr&&root->right==nullptr时，递归root->left并+1
最后，两种情况都不属于的，则递归左右子树，比较最小，然后返回并+1。
110.平衡二叉树
题目链接
解法类似于求树的最大深度，但有两个不同的地方：一是我们需要先处理子树的深度再进行比较(判断是否是平衡二叉树)，二是如果我们在处理子树时发现其已经不平衡了，则可以返回一个-1，使得所有其长辈节点可以避免多余的判断。
int height(TreeNode *root){if (root==0)return 0;int lefth=height(root->left), righth=height(root->right);if (lefth==-1 || righth==-1 || abs(lefth-righth)>1)return -1;return 1+max(lefth,righth);}bool isBalanced(TreeNode* root) {return height(root)>=0;}
543.二叉树的直径
题目链接
待更新的最长直径值是经过该子树根节点的最长
直径（即两侧长度）；而函数返回值是以该子树根节点为端点的最长直径值（即一侧长度），使用
这样的返回值才可以通过递归更新父节点的最长直径值）。
int diameterOfBinaryTree(TreeNode* root) {
int diameter=0;
helper(root,diameter);
return diameter;
}
int helper(TreeNode *root, int& diameter){
if (root==nullptr)
return 0;
int l=helper(root->left,diameter), r=helper(root->right,diameter);
diameter=max(l+r,diameter);
return max(l,r)+1;
}
437.路径总和|||
题目链接
递归有两种搜集数值的方式，一种是向下递深时，以传引用的方式，一种是向上归时，将需要的值作为函数返回值给返回回去。
这里只能通过双递归函数来暴力遍历和求解，因为每一种情况都需要考虑。
一种优化方式是把Helper的sum给去掉，而是直接用targetSum是否等于0来判断是否达到目标值，递归时，是targetSum-root->val;
int pathSum(TreeNode* root, int targetSum) {
if (root==nullptr)
return 0;
return pathSum(root->left,targetSum)+pathSum(root->right,targetSum)+Helper(root,targetSum,0);
}
int Helper(TreeNode *root, int targetSum,int sum) {
if (root==nullptr)
return 0;
int sums=Helper(root->left,targetSum,sum+root->val)+Helper(root->right,targetSum,sum+root->val);
if (sum+root->val==targetSum)
return sums+1;
else
return sums;
}
101.对称二叉树
题目链接
方法一:递归的地方 对于两个节点，如果这两个节点的值相等，并且左节点的左子树等于右节点的右子树，左节点的右子树等于右节点的左子树，则是镜像
方法二:用迭代代替递归 引入一个队列，初始时把根节点入队两次， 每次出队两个节点并比较它们的值，然后将节点A的左节点入队，另一个结点B的右节点入队，A节点的右节点入队，B节点的左节点入队 循环这个过程。 当队列为空或者检测到树不对称时，算法结束。
637.二叉树的层平均值
题目链接
采用队列的形式实现层序遍历，也即广度优先搜索，同时要计数上一层的节点数，保证只有同一层的节点才会被出队列。
669.修剪二叉搜索树
题目链接
利用二叉搜索树的性质，进行修剪
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root==nullptr)
return root;
if (root->val>high)
return trimBST(root->left,low,high); //因为节点值比high高，满足条件的分支一定来自于该节点的left
if (root->val<low)
return trimBST(root->right,low,high); //节点值比low低，则满足条件的分支一定来自于该节点的right
root->left=trimBST(root->left,low,high); //下面这两个是满足条件的root，则直接可以递归后再返回
root->right=trimBST(root->right,low,high);
return root;
}
617.合并二叉树
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1==nullptr)
return root2;
if (root2==nullptr)
return root1;
root1->val=root1->val+root2->val; //统一都归到root1上去，由root1来进行返回
root1->left=mergeTrees(root1->left,root2->left); //保证root1的左子树满足条件
root1->right=mergeTrees(root1->right,root2->right); //保证root1的右子树满足条件
return root1; //作为满足条件的root1返回
}
572.另一个树的子树
题目链接
采用对主树的每一个节点作为根节点的子树和所给的树进行相等判断
538.把二叉搜索树转换为累加树
题目链接
二叉搜索树的中序遍历是一个单调递增的有序序列。如果我们反序地中序遍历该二叉搜索树，即可得到一个单调递减的有序序列。
本题将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。
530.二叉搜索树的最小绝对差-(中序遍历)
题目链接
二叉搜索树进行中序遍历可以得到递增序列，则节点差的绝对值的最小值一定在这个递增序列中相邻的两个之间，因此在用递归时，可以用pre记录一下上次中序遍历的节点值，用diff记录当前最小绝对差即可。
int getMinimumDifference(TreeNode* root) {
int diff=-1;
int pre=-1;
Helper(root,diff,pre);
return diff;
}
void Helper (TreeNode *root, int &diff, int &pre) {
if (root!=nullptr) {
Helper(root->left,diff,pre);
if (pre!=-1&&diff==-1) {
diff=root->val-pre;
}
if (pre!=-1&&diff!=-1) {
diff=((root->val-pre)>diff)? diff :(root->val-pre);
}
pre=root->val;
Helper(root->right,diff,pre);
}
return;
}
235.二叉搜索树的最近公共祖先
题目链接
利用二叉搜索树的性质即可。
小技巧，预先处理一下p和q的大小关系，这样在后续判断时会很方便。
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode *minptr, *maxptr;
maxptr=(p->val>q->val)? p : q;
minptr=(p->val<q->val)? p : q;
return Helper(root,minptr,maxptr);
}
TreeNode* Helper(TreeNode *root, TreeNode *minptr, TreeNode *maxptr) {
if (root==nullptr)
return root;
if (root->val<=maxptr->val&&root->val>=minptr->val)
return root;
if (root->val<minptr->val)
return Helper(root->right,minptr,maxptr);
if (root->val>maxptr->val)
return Helper(root->left,minptr,maxptr);
return root;
}
450.删除二叉搜索树中的节点
题目链接
注意，在采用替换值的方式时，就不能利用BST的左右走一边的性质了，因为被替换掉后，局部就不满足BST的构造，只能左子树和右子树都要遍历。
或者在发现要删除的节点前，可以用左右走一边性质；在发现要删除的节点后，需要替换的递归时，另写一个递归函数，在该函数里不用左右走一边性质，而是左右子树都遍历。
129.求根节点到叶节点数字之和-(深优)
- 全局变量sum保存数字之和，每次深度优先遍历到叶子节点时，把计算得到的数字加到sum上。
- 利用每次往下递归，把当前值cur*10，这样就可以实现根据树的深度来计算位数
void Helper(TreeNode*root, int&sum,int cur) { cur=cur+root->val; //将该层加入 if (root->left==nullptr&&root->right==nullptr){ sum=sum+cur; return; } cur=cur*10; //如果还有下一层存在，说明得把cur往前乘10 if (root->left!=nullptr) Helper(root->left,sum,cur); if (root->right!=nullptr) Helper(root->right,sum,cur); return; } int sumNumbers(TreeNode* root) { int sum=0; Helper(root,sum,0); return sum; }
若有收获，就点个赞吧
0 人点赞
