02二叉树的操作
# 02 二叉树的操作
# 226 翻转二叉树 (opens new window)
翻转一棵二叉树
输入一棵二叉树,输出一棵左右子树的位置跟输入正好相反的二叉树
输入:
4 / \ 2 7 / \ / \ 1 3 6 9
输出:
4 / \ 7 2 / \ / \ 9 6 3 1
解析:
本题是一道经典的递归问题,我们采用自下而上的递归策略,从叶子节点开始交换左右节点。如果当前根节点 root 的左右子树都已经完成了翻转,那么仅需要交换两个子树的位置即可,即交换 root 左右节点的指向,就可以完成整颗子树的翻转。递归的终止条件:当前节点为 null
时返回。
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root){
return root;
}
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
# 617 合并二叉树 (opens new window)
给定两个二叉树,将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
输入两个二叉树,输出一个合并后的新二叉树
输入:
Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7
输出: 合并后的树
3 / \ 4 5 / \ \ 5 4 7
解析:
本题可以采用自上而下的递归策略,将Tree2的当前根节点 root2 的值合并到Tree1的当前根节点 root1 上,然后递归合并roo1和roo2根节点的左节点,递归合并roo1和roo2根节点的右节点,最终只保存 Tree1作为合并后的新二叉树。
递归的终止条件是当前根节点roo1和roo2有至少一个为空,直接返回非空节点作为新二叉树的节点,均为空则返回空节点。
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(!root1 || !root2){
return root1?root1:root2;
}
root1->val += root2->val;
root1->left = mergeTrees(root1->left,root2->left);
root1->right = mergeTrees(root1->right,root2->right);
return root1;
}
};
# 1110 删点成林 (opens new window)
给定一个整数二叉树和一些整数,求删掉这些整数对应的节点后,剩余的子树。
输入是一个整数二叉树和一个一维整数数组,输出一个数组,每个位置存储一个子树(的根节点)。
输入:root = [1,2,3,4,5,6,7], to_delete = [3,5] 输出:[[1,2,null,4],[6],[7]
解析:
本题核心递归逻辑就是当前节点是否要被删除,如果删除就将其左右子数加入结果集,不删除就直接返回该节点。
使用一个节点数组存储结果集,使用哈希表存储删除节点,便于检验当前节点是否要被删除。
递归过程中自底向上:将递归调用写在处理过程之前实现自底向上的处理
从下层节点开始判断是否要被删除:
- 如果删除就将其左右子数加入结果集,并将指向该节点的指针置为空
- 不删除就直接返回该节点
最终如果原树的根节点没有被删除将其加入森林
class Solution {
public:
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
// 使用一个节点数组存储所有可能的根节点
vector<TreeNode*> forest;
// 使用哈希表存储删除节点,便于查找检验
unordered_set<int> hash(to_delete.begin(),to_delete.end());
// 递归处理原树,删点成林
root = helper(root,hash,forest);
// 如果原树的根节点没有被删除将其加入森林
if(root){
forest.push_back(root);
}
return forest;
}
TreeNode* helper(TreeNode* root, unordered_set<int>& hash, vector<TreeNode*>& forest){
if(!root){
return root;
}
// 递归处理左右子树
root->left = helper(root->left, hash, forest);
root->right = helper(root->right, hash, forest);
// 如果当前根节点要被删除,则将其左右子树加入森林
if(hash.find(root->val)!=hash.end()){
if(root->left){
forest.push_back(root->left);
}
if(root->right){
forest.push_back(root->right);
}
// 删除根节点
root = NULL;
}
// 当前根节点不用删除,这直接返回该节点
return root;
}
};
上次更新: 2023/11/19, 12:55:48