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