226.翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：输入：root = [2,1,3] 输出：[2,3,1]
示例 3：输入：root = [] 输出：[]
分析:
1.尝试用两种思维解决这个问题
2.遍历思维, 从上往下翻转
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* intermediary = root->left;
root->left = root->right;
root->right = intermediary;
invertTree(root->left);
invertTree(root->right);
return root;
}
};
3.采用分解问题的思维, 原问题翻转之后的效果等于左子树翻转完, 右子树翻转完之后再左右翻转
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return root;
}
TreeNode* lInverted = invertTree(root->left);
TreeNode* rInverted = invertTree(root->right);
root->left = rInverted;
root->right = lInverted;
return root;
}
};
116.填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} };填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
分析:
1.这道题用层次遍历可解, 看能否用直接遍历求解
2.同一个父节点的两个叶子节点是能关联的, 不属于同一个父节点的叶子节点怎么关联?
3.假如我们只需要把同一个父节点的两个节点关联起来, 只需要递归地进行串联
void dfs(Node* leftNode, Node* rightNode) {
if (leftNode == nullptr || rightNode == nullptr) {
return;
}
leftNode->next = rightNode;
dfs(leftNode->left, leftNode->right);
dfs(rightNode->left, rightNode->right);
return;
}
4.上述做法可以把任何一个节点的左右节点关联起来, 但不能将非同一个根节点关联起来, 怎么将非同一个根节点关联起来呢?
只需要在遍历的时候多一个操作traverse(leftNode->right, rightNode->left)
void dfs(Node* leftNode, Node* rightNode) {
if (leftNode == nullptr || rightNode == nullptr) {
return;
}
leftNode->next = rightNode;
dfs(leftNode->left, leftNode->right);
dfs(rightNode->left, rightNode->right);
dfs(leftNode->right, rightNode->left);
return;
}
完整答案
class Solution {
public:
void dfs(Node* leftNode, Node* rightNode) {
if (leftNode == nullptr || rightNode == nullptr) {
return;
}
leftNode->next = rightNode;
dfs(leftNode->left, leftNode->right);
dfs(rightNode->left, rightNode->right);
dfs(leftNode->right, rightNode->left);
return;
}
Node* connect(Node* root) {
if (root == nullptr) {
return root;
}
dfs(root->left, root->right);
return root;
}
};
114.二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。示例 1：输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：输入：root = [] 输出：[]
示例 3：输入：root = [0] 输出：[0]
分析:
1.先理解一下二叉树转换为链表是什么意思 ? 链表本质上就是只有一个子树的二叉树, 二叉树就是链表的第一个节点多开出来一条链表的链表
2.可以用递归/非递归先序遍历, 遍历过程中把元素存储到数组里面, 然后再遍历这个数组构建一个二叉树; 能否使用分解的方式去实现?
class Solution {
private:
vector<TreeNode*> list;
public:
// 先序转数组
void preorderTraverse(TreeNode* root) {
if (root == nullptr) {
return;
}
list.push_back(root);
preorderTraverse(root->left);
preorderTraverse(root->right);
return;
}
void flatten(TreeNode* root) {
preorderTraverse(root);
int len = list.size();
// 迭代构建树: 左孩子置空指针, 右孩子链接起来
for (int i = 1; i < len; ++i) {
TreeNode* pre = list[i-1];
TreeNode* cur = list[i];
pre->left = nullptr;
pre->right = cur;
}
return;
}
};
2.思考能否用分解的思路递归实现, 那么就要看看怎么去实现 flatten 这种操作, 也就是找 flatten 子树和当前根节点的关系
3.如下所示 一个flatten操作可以分解为 3 步, 先把左右子树分别做 flatten, 然后将右子树接在左子树的最下面, 然后把左子树换到右子树
1 1 1
/ \ / \ \
2 5 2 5 2
/ \ \ \ \ \
3 4 6 3 6 3
\ \
4 4
\
5
\
6
将三步都写出来, 得到完整答案
class Solution {
public:
void flatten(TreeNode* root) {
if (root == nullptr) {
return;
}
flatten(root->left);
flatten(root->right);
TreeNode* left = root->left;
TreeNode* right = root->right;
root->left = nullptr;
root->right = left;
TreeNode* p = root;
while (p ->right != nullptr) {
p = p->right;
}
p->right = right;
return;
}
};
652.寻找重复的子树
给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。示例 1：输入：root = [1,2,3,4,null,2,4,null,null,4] 输出：[[2,4],[4]]
示例 2：输入：root = [2,1,1] 输出：[[1]]
示例 3：输入：root = [2,2,2,3,null,3,null] 输出：[[2,3],[3]]
分析:
1.遍历可以得到所有的子树, 对每个子树进行序列化
2.序列化的一般操作可以写成这样的字符串 “x(左子树序列化的结果)(右子树序列化的结果)”
3.在 set 中保存重复元素时, 必须保证不是统一个 node 的同一类 node 插入的是一个相同的结构, 用 set 保存已有的结果, 这里必须用一个 map 去保存已经见到过的结果; 如果用 set 直接保存 node, 那么相同的子树会保存不同的节点
class Solution {
private:
unordered_set<TreeNode*> repeat;
unordered_map<string, TreeNode*> seen;
public:
string dfs(TreeNode* node) {
if (node == nullptr) {
return "";
}
string serial = to_string(node->val) + "(" + dfs(node->left) + ")" + "(" + dfs(node->right) + ")";
auto it = seen.find(serial);
// 找到重复子树
if (it != seen.end()) {
repeat.insert(it->second);
// 注意这里只能插入统一类子树的标准化形式比如第一次存放的形式, 而不是插入node
// 不然会被判定为两个子树不一样
// repeat.insert(node);
} else {
seen[serial] = node;
}
return serial;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
dfs(root);
vector<TreeNode*> ans;
ans.assign(repeat.begin(), repeat.end());
return ans;
}
};
101.对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：输入：root = [1,2,2,null,3,null,3] 输出：false
分析:
1.采用分解的思维: 对于原问题来说, 给定一个根节点, 需要判定左子树和右子树是对称的, 怎么判定左子树和右子树是对称的
2.要想判定左子树和右子树对称性, 需要生成两个指针来同时遍历, 一个向左一个向右, 然后1生2, 2生4, 4生成8…
class Solution {
public:
// p 和 q 是两个同时遍历具有对称性的指针
bool check(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) {
return true;
}
if (p == nullptr || q == nullptr) {
return false;
}
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
3 / \ 5 1 / \ / \ 6 2 0 3 / \ 7 4示例 2：输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：输入：root = [1,2], p = 1, q = 2 输出：1
分析:
1.给定一个根节点, 然后给定树里面任意两个节点, 让我们找这两个任意节点的最低公共祖先
2.先可以判定一些非常简单的情况, 假设 p 和 q 之间本身有一个祖先关系, 也就是说 root == p || root = q 那么就说明这时候的 root 就是最近公共祖先
3.然后我们处理一些相对复杂的情况, 根节点在上面, 然后 p 和 q 在根节点的下面分布着, 下一步怎么搜索呢 ? 根节点的搜索指针可以向下移动, 可以从根节点左子树搜索 p 和 q, 也可以从根节点的右子树搜索 p 和 q; 这里有 3 种可能的情况,
(i). p 和 q 都在左子树, 那么我们就在 左子树里面递归找最低公共祖先
(ii). p 和 q 都在右子树, 那么我们就在 右子树里面递归找最低公共祖先
(iii). p 和 q 左右子树各一个, 最低公共祖先就是 root
class Solution {
public:
bool nodeInSubTree(TreeNode* root, TreeNode* c) {
if (root == nullptr) {
return false;
}
if (root == c) {
return true;
}
return nodeInSubTree(root->left, c) || nodeInSubTree(root->left, c);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) {
return nullptr;
}
if (root == p || root == q) {
return root;
}
if (nodeInSubTree(root->left, p) && nodeInSubTree(root->right, q)) {
return lowestCommonAncestor(root->left, p, q);
}
if (nodeInSubTree(root->right, p) && nodeInSubTree(root->right, q)) {
return lowestCommonAncestor(root->right, p, q);
}
return root
}
};
4.我们再想一下, 既然总共就 以上 3 种情况, 这里我们也不用非要判断 p 和 q 具体要在哪个子树里面: 情况还是如上三种, 我们逐次判断 2 种情况的存在性就可以
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) {
return nullptr;
}
if (root == p || root == q) {
return root;
}
TreeNode* lRes = lowestCommonAncestor(root->left, p, q);
TreeNode* rRes = lowestCommonAncestor(root->right, p, q);
if (lRes != nullptr && rRes != nullptr) {
return root;
} else if (lRes == nullptr) {
return rRes;
} else {
return lRes;
}
}
};
转载请注明来源, from goldandrabbit.github.io
