二叉树问题（三）-LeetCode 669、951、662、199、538、236（中序，层次遍历）
二叉树问题（三）-LeetCode 669、951、662、199、538、236（中序，层次遍历）
作者：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