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