专题: 二叉树题目总结

作者 Lucyyang 日期 2020-03-15
专题: 二叉树题目总结

忘记昨天,也不要痴想明天。

看了学习算法和刷题的思路指南中的第四部分,其实很多比较难一点的算法问题,本质上都是树的问题。好好练习树可以对后面解体有很大的帮助。

所以,很开心能开始总结二叉树专题啦!因为递归对我来说是薄弱环节,二叉树的一些题目对我还是颇有难度的。从我自己做题的经验,二叉树的题目基本可以分为用BFS和DFS进行递归解决。下面就从易到难总结一下做过的一些典型题目。

树的定义如下:

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

首先给出一个简单基本框架吧:

void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}

在对应的注释那对root进行处理就对应着这种遍历方式。

树的遍历

首先来看和树的遍历相关的部分,最简单的就是直接给出一种遍历方式:

Binary Tree Inorder Traversal

题目: LC94,给定一棵二叉树,按中序遍历返回节点值。

方法: 最直接的做法就是递归,按照左根右的顺序进行遍历。

代码:

class Solution {
public:
vector<int> res;
void inoder(TreeNode* root){
if(root == NULL)
return;
inoder(root->left);
res.push_back(root->val);
inoder(root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
inoder(root);
return res;
}
};

相似的题目还有前序遍历后序遍历

Binary Tree Level Order Traversal

题目:L102,还有一类典型的遍历方式是按层遍历。

方法:使用queue来保存树的节点,对于每一次的循环来说,可以先获得queue中的节点数,就是该层的nodes。

代码:

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root) return vector<vector<int>>(0,vector<int>(0));
queue<TreeNode*> q;
q.push(root);
vector<vector<int>> res;
TreeNode* cur = nullptr;
while(!q.empty()){
int s = q.size();
vector<int> temp;
for(int i=0;i<s;i++){
cur = q.front();
q.pop();
temp.push_back(cur->val);
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
res.push_back(temp);
}
return res;
}
};

还有类似的对N叉树进行层遍历,参见LC429

Vertical Order Traversal of a Binary Tree

题目:LC314 遍历方式还有一种题目,按照垂直方式打印节点。

方法:依然按照层的方式进行遍历,但是有个小trick:queue中存储的为pair<int, TreeNode>,用于记录竖直方向上的level id*。此外用一个map将不同的level id和值的集合关联起来。注意map有自动排序的特点。

代码:

class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
map<int, vector<int>> m; //此处注意Map自动排序的特性
queue<pair<int, TreeNode*>> q;
q.push({0, root});
while(!q.empty()) {
auto a = q.front();
q.pop();
m[a.first].push_back(a.second->val); // m[id] means the same level
if(a.second->left) q.push({a.first-1, a.second->left});
if(a.second->right) q.push({a.first+1, a.second->right});
}
for (auto a: m) {
res.push_back(a.second); //a is new variable,m已经根据key自动排序了
}
return res;
}
};

类似题目还有LC987

构建二叉树

接下来难度升级,给定前序中序,让生成出二叉树:

Construct Binary Tree I

题目: LC105,给定前序中序遍历,构造出一棵二叉树。

方法: 首先我们能知道前序遍历数组的第一个节点preorder[0]一定是树的根节点,而且也一定在inorder数组中存在,那就假设成preorder[0] = inoder[k]好了。而中序遍历最大的特点就是从根节点开始将左右子树分开,即k左边的就是根节点左子树的中序遍历、k右边的就是根节点右子树的中序遍历。这样我们也知道了根节点左子树的个数,即从0到k-1,右子树为k+1到inorder数组末尾。则对于preorder,从preorder[1]到preorder[k+1]都是该树的左子树,剩下的最后一部分就是根节点右子树的前序遍历。接下来就是分治的思想,将规模较大的问题分解成为两个较小的问题,然后递归的进行处理,还原左子树和右子树,最后连通根节点一起组成一棵完整的树。

代码:

class Solution {
public:
TreeNode* divide(vector<int>& preorder, vector<int>& inorder,
int lp,int rp,int li,int ri){
if(lp>rp) return NULL;
TreeNode* root = new TreeNode(preorder[lp]); //建立根节点
// find in inorder [li,ri]
for(int i=li; i<=ri;i++){
// 寻找中序遍历中根节点的位置,这样才能知道左右子树个数
if(inorder[i]==preorder[lp]){
// 已知root在inorder中位置为i,则左子树有i-1-li+1(包含i-1和li,要加1)个元素
// 而preorder从lp+1算起的i-li个元素
root->left = divide(preorder,inorder,lp+1,lp+i-li,li,i-1);
root->right = divide(preorder,inorder, lp+i-li+1,rp,i+1,ri);
}
}
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return divide(preorder,inorder,0,int(preorder.size())-1,0,int(inorder.size())-1);
}
};

Construct Binary Tree II

题目:LC106,接下来稍作变形,给定中序遍历和后序遍历,构建二叉树。

方法:和上述方法类似,只是对于后序遍历,根节点放在最后,因此更新左右子树时需要注意数组边界范围。

代码:

class Solution {
public:
TreeNode* divide(vector<int>& inorder, vector<int>& postorder, int li, int ri, int lp, int rp){
if(lp>rp) return NULL;
TreeNode* node = new TreeNode(postorder[rp]);
for(int i=li;i<=ri;i++){
if(inorder[i]==postorder[rp]){
node->left = divide(inorder,postorder,li,i-1,lp,lp+i-li-1);
node->right = divide(inorder,postorder,i+1,ri,lp+i-li,rp-1);
}
}
return node;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return divide(inorder,postorder,0,int(inorder.size())-1,0,int(postorder.size())-1);
}
};

Convert Sorted Array to BST

题目:LC108,将有序数组转为二叉搜索树,即保证所有左子树的值比root->val小,所有右子树的值比root->val大。

方法:对于这道题的核心,就是要找到一个根节点,使得全部左子树值比它小,全部右子树值比它大,那哪一个数最合适呢?当然是数组的中间数,将中间数构建成根节点后,左子树则通过数组前半部分构建,右子树通过数组后半部分构建。

代码:

class Solution {
public:
TreeNode* buildTree(vector<int>& nums, int start, int end){
if(start>end) return NULL;
TreeNode* root = new TreeNode(0);
int mid = start + (start-end)/2;
root->val = nums[mid];
root->left = buildTree(nums,start,mid-1);
root->right = buildTree(nums,mid+1,end);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.empty()==true) {return NULL;}
TreeNode* root;
root = buildTree(nums,0,int(nums.size())-1);
return root;
}
};

这道题在周赛180第三题中有个follow up,如何将二叉搜索树构建成平衡二叉搜索树

Recover Binary Search Tree

题目:LC99,要求不改变树的结构,返回一个搜索二叉树。

方法:这题有个小trick,中序遍历的时候将节点也保存在vector中,然后将值进行排序。再对节点一一赋值,这样最先被赋值的就是左子树,也就是最小值,中间root被赋予中间的数值,右子树会被赋予数组后半部分较大的值。

class Solution {
public:
vector<int> vals;
vector<TreeNode*> nodes;
void inorder(TreeNode* root){
if(root == NULL)
return;
inorder(root->left);
vals.push_back(root->val);
nodes.push_back(root);
inorder(root->right);
}
void recoverTree(TreeNode* root) {
inorder(root);
sort(vals.begin(), vals.end());
for(int i = 0; i < nodes.size(); i++) {
nodes[i]->val = vals[i];
}
}
};

Unique Binary Search Trees

题目:L95,TODO

树的判定

这类题目主要是来判断树的特性。

Same Tree

题目:L100,判断两棵树是否相同。

方法:递归check,每次检查nodes都存在并且值相等,否则返回false。

代码:

class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==NULL&&q==NULL){
return true;
}else if(p==NULL||q==NULL){
// 上一个已经判断了p是NULL还是q是NULL
return false;
}else if(p->val!=q->val)
return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
};

Validate Binary Search Tree

题目:L98判断一棵树是否为二叉搜索树。

方法:设立下限和上限,每次判断节点值是否在上下限之内,对于左右子树分别更新上下界限。如果左右子树都为true,该节点返回true。

代码:

class Solution {
public:
bool helper(TreeNode* node, int lower_limit, int upper_limit){
if(node==NULL) return true;
if((lower_limit!=-1) && (node->val <=lower_limit))
return false;
if((upper_limit!=-1)&&(upper_limit<=node->val))
return false;
bool left = node->left!=NULL? helper(node->left,lower_limit,node->val):true;
bool right=node->right!=NULL? helper(node->right,node->val,upper_limit):true;
return left&&right;
}
bool isValidBST(TreeNode* root) {
if(root==NULL) return true;
return helper(root,-1,-1);
}
};

Check Completeness of a Binary Tree

题目:LC958,检查一棵树的完整性,即左子树为空的情况下,右子树不可有值。

方法:这题的关键在于设置一个bool seennull,然后按层遍历。对于每层的节点,如果左子树为空,则seennull为true,如果之后右子树不为空,则返回false。这题的做法还可以进一步简化,树的完整性其实就是中间不能出先null节点,如果一旦出现null节点,我们将seennull设为true,如果之后发现还有节点,则返回false。这样就不用考虑每层的节点问题了。

代码:

class Solution {
public:
bool isCompleteTree(TreeNode* root) {
queue<TreeNode*> que;
que.push(root);
bool seennull = false; //这个是判断的一个关键
while(!que.empty()) {
TreeNode *cur = que.front();
que.pop();
if(cur == NULL) {
if(!seennull) seennull = true;
continue;
}else { //cur != NULL
if(seennull == true) return false;
}
que.push(cur->left); //if left is null, push null and check in the next //round, if we found it is null, seennull = true. if right is not null, return //false.
que.push(cur->right);
}
return true;
}
};