226 翻转二叉树
翻转一棵二叉树
输入一棵二叉树,输出一棵左右子树的位置跟输入正好相反的二叉树
输入:
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 合并二叉树
给定两个二叉树,将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 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 删点成林
给定一个整数二叉树和一些整数,求删掉这些整数对应的节点后,剩余的子树。
输入是一个整数二叉树和一个一维整数数组,输出一个数组,每个位置存储一个子树(的根节点)。
输入: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;}
};
参考资料
LeetCode 101:和你一起轻松刷题(C++) 第 14 章 指针三剑客之树
更多推荐
二叉树,操作,笔记,LeetCode
发布评论