LeetCode刷题笔记二叉树二叉树的操作

编程入门行业动态更新时间:2024-10-27 03:40:22

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;}
};