作者:TeddyZhang,公众号:算法工程师之路
二叉树问题(三):
LeetCode # 669 951 662 199 538 236
1
编程题
【LeetCode #669】修剪二叉搜索树
给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。
/**
* 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:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if (root == nullptr) return root;
// 处理异常节点,将root->right提升为root
if (root->val < L)
return trimBST(root->right, L, R);
if (root->val > R)
return trimBST(root->left, L, R);
// 处理正常的节点
root->left = trimBST(root->left, L, R);
root->right = trimBST(root->right, L, R);
return root;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/trim-a-binary-search-tree
【LeetCode #951】翻转等价二叉树
我们可以为二叉树 T 定义一个翻转操作,如下所示:选择任意节点,然后交换它的左子树和右子树。 只要经过一定次数的翻转操作后,能使 X 等于 Y,我们就称二叉树 X 翻转等价于二叉树 Y。 编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1 和 root2 给出。
示例: 输入:root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7] 输出:true 解释:We flipped at nodes with values 1, 3, and 5.
解题思路:
由于该二叉树经过多次翻转可以重合,因此要么是一棵树的左子树等于另一个的左子树,或者一棵树的左子树等于另一棵树的右子树。如果对应根节点不相同,那么永远也不会重合,返回false即可。
/**
* 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 flipEquiv(TreeNode* root1, TreeNode* root2) {
if (root1 == root2) return true;
if (root1 == nullptr && root2 != nullptr) return false;
if (root1 != nullptr && root2 == nullptr) return false;
if (root1->val != root2->val) return false;
return flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left)
|| flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right);
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flip-equivalent-binary-trees
【LeetCode #662】二叉树最大宽度
给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。
每一层的宽度被定义为两个端点(该层最左和最右的非空节点,两端点间的null节点也计入长度)之间的长度。
解题思路:
每层的索引值都从1开始,也就是如果某一个节点的索引为i,则其左孩子索引为(2*i - 上层最开始的节点索引),这样可以重置索引,避免二叉树节点过多导致索引值溢出。 然后当访问到最右边不是nullptr的节点,才进行宽度的计算。注意访问最右边不是nullptr节点时,size正好递减为0.
/**
* 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:
int widthOfBinaryTree(TreeNode* root) {
using PairNode = pair<TreeNode*, int>;
int res = INT_MIN;
queue<PairNode> que;
que.push(make_pair(root, ));
while(!que.empty()) {
int size = que.size();
int i = que.front().second;
while(size--) {
PairNode tmp = que.front();
que.pop();
if (size == ) // 只有size等于0时,才会访问到每层最右边不为nullptr的节点,此时计算width
res = max(res, tmp.second - i + );
// 每一层都从 1 开始
if (tmp.first->left)
que.push(make_pair(tmp.first->left, tmp.second* - i));
if (tmp.first->right)
que.push(make_pair(tmp.first->right, tmp.second*+ - i));
}
}
return res;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-width-of-binary-tree
【LeetCode #199】二叉树的右视图
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
解题思路:
使用层序遍历,不同是的,我们需要将每一层的节点从右向左送入队列中,然后一次处理整个一层数,在处理之前,向vector中压入第一个节点的值(也就是每层最右边那一个)。
/**
* 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:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (root == nullptr) return res;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
res.push_back(que.front()->val);
while(size--){
TreeNode* tmp = que.front();
que.pop();
// 从右向左入队列
if (tmp->right) que.push(tmp->right);
if (tmp->left) que.push(tmp->left);
}
}
return res;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-right-side-view/
【LeetCode #538】把二叉搜索树变成累加树
给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
解题思路:
对于原来的中序遍历,是:左 --> 根 --> 右,对于这道题目而言,我们需要从右边开始,然后依次累加并赋值。
(递归法)
/**
* 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:
int sum = ;
TreeNode* convertBST(TreeNode* root) {
if (root == nullptr) return nullptr;
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
return root;
}
};
(迭代版)
/**
* 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:
int sum = ;
TreeNode* convertBST(TreeNode* root) {
stack<TreeNode*> sta;
TreeNode* cur = root;
while(cur != nullptr || !sta.empty()) {
if (cur != nullptr) {
sta.push(cur);
cur = cur->right; // 与之前的中序遍历正好相反
} else {
cur = sta.top();
sta.pop();
sum += cur->val;
cur->val = sum;
cur = cur->left;
}
}
return root;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/convert-bst-to-greater-tree
【LeetCode #236】二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
解题思路:
首先找出根节点到p, q两个节点的二叉树路径,然后再根据路径进行匹配,最后一个相同的元素即为公共祖先。 注意路径的元素为指针(地址), 由于使用val的话会有冲突的缺点。
class Solution {
private:
bool dfs(vector<TreeNode*>& path, TreeNode* root, TreeNode* find) {
if (root == nullptr) return false;
path.push_back(root);
if (root == find) {
return true;
}
if (dfs(path, root->left, find)) return true;
if (dfs(path, root->right, find)) return true;
path.pop_back();
return false;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> ll, rr;
if(!dfs(ll, root, p) || !dfs(rr, root, q)) return nullptr;
int i = ;
for (; i < ll.size() && i < rr.size(); i++) {
if (ll[i] != rr[i]) return ll[i-1];
}
return ll[i-1];
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree