大前端

前端学习之家-大前端

LeetCode刷题笔记 二叉树 树的递归

​ 最为常见的树就是二叉树,这种树的每个节点最多有两个子节点,二叉树可以看成是单链表的升级版,因为他和链表的主要区别就是多了一个子节点的指针。

 Definition for a binary tree node.
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };

104 二叉树的最大深度

求一个二叉树的最大深度。

输入是一个二叉树,输出是一个整数,表示该树的最大深度。

输入: [3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7

输出:3

解释:返回它的最大深度 3

解析:

​ 采用深度优先搜索,其子问题是:左子树和右子树的最大深度 l 和 r,那么该二叉树的最大深度即为 max(l,r)+1。中止条件是访问的节点为空,推出递归。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root){
            return 0;
        }
        return max(maxDepth(root->left),maxDepth(root->right)) + 1;
    }
};

110 平衡二叉树

判断一个二叉树是否平衡。树平衡的定义是,对于树上的任意节点,其两侧节点的最大深度的差值不得大于 1。

输入是一个二叉树,输出一个布尔值,表示树是否平衡。

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

解析:

​ 本题的思路类似104 二叉树的最大深度,不同的是在获取子树深度时要对当前左右子树的深度进行比较,如果还未遍历完二叉树就已经发现左右子树不平衡,则直接返回-1,避免再继续往下计算子树深度。

​ 提前返回-1中断子树深度计算要注意的是:第一次返回-1的判断条件是abs(left - right) > 1,但是在往上回溯深度计算结果的过程中,如果出现了中断,那么回溯结果为 -1,这时表明下层子树出现了不平衡情况,所以上层返回-1的判断条件是left == -1 || right == -1

class Solution {
public:
    int treeDepth(TreeNode* node){
        if(!node){
            return 0;
        }
        int l = treeDepth(node->left);
        int r = treeDepth(node->right);
        if(l==-1 || r==-1 || abs(l-r)>1){
            return -1;
        }
        return max(l,r)+1;
    }

    bool isBalanced(TreeNode* root) {
        return treeDepth(root) != -1;
    }
};

543 二叉树的直径

求一个二叉树的最长直径。直径的定义是二叉树上任意两节点之间的无向距离。

输入是一个二叉树,输出一个整数,表示最长直径。

输入:给定二叉树

1 
/ \
2  3
/ \    
4  5    

输出: 3

解释:它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

解析:

​ 本题可以直接转化为左子树最大深度与右子树最大深度之和,所以在递归计算子树深度时,更新的最长直径值和递归返回的值是不同的。这是因为待更新的最长直径值是经过该子树根节点的最长直径(即两侧长度);而函数返回值是以该子树根节点为端点的最长直径值(即一侧长度),使用这样的返回值才可以通过递归更新父节点的最长直径值)。

class Solution {
public:
    int maxDepth(TreeNode* root, int& diameter){
        if(!root){
            return 0;
        }
        int l = maxDepth(root->left,diameter);
        int r = maxDepth(root->right,diameter);
        // 更新当前节点的最长直径
        diameter = max(l+r,diameter);
        return max(l,r)+1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        maxDepth(root,diameter);
        return diameter;
    }
};

101 对称二叉树

判断一个二叉树是否对称。

输入一个二叉树,输出一个布尔值,表示该树是否对称。

输入:给定二叉树

   1
  / \
 2   2
/ \ / \
3  4 4  3

输出:true

解释:二叉树 [1,2,2,3,4,4,3] 是对称的

解析:

​ 本题可以将二叉树是否对称转化为其左右子树是否对称,本质上还是树的递归问题,但是递归过程中涉及到比较。对两个子树进行比较判断是否相等或对称的解法一般可以按照如下四步:

  • 如果两个子树都为空指针,则它们相等或对称,从根节点递归到叶子节点时都是相等的
  • 如果两个子树只有一个为空指针,则它们不相等或不对称,一棵子树却胳膊少腿肯定不相等
  • 如果两个子树根节点的值不相等,则它们不相等或不对称,出现比较位置不同值直接返回false
  • 根据相等或对称要求,进行递归处理;相等就是左子树的左节点和右子树的左节点比较,左子树的右节点和右子树的右节点比较;对称就是左子树的左节点和右子树的右节点比较,左子树的右节点和右子树的左节点比较

​ 需要注意的是前三个判断步骤不能调换顺序,因为有一个为空范围大于均为空,如果有空就无法取值。

class Solution {
public:
    bool isSymmetric(TreeNode* left, TreeNode* right){
        if(!left && !right){
            return true;
        }else if(!left || !right){
            return false;
        }else if(left->val != right->val){
            return false;
        }
        return isSymmetric(left->left,right->right) && isSymmetric(left->right,right->left);
    }

    bool isSymmetric(TreeNode* root) {
        if(!root){
            return true;
        }
        return isSymmetric(root->left,root->right);
    }
};

572 另一棵树的子树

给定两棵二叉树 rootsubRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树

输入两棵二叉树,输出一个布尔值表示 root 树中是否包含 subRoot 树

输入:root = [3,4,5,1,2], subRoot = [4,1,2]

	Tree root                  Tree subRoot               
      3                         4                             
      / \                       / \                            
     4   5                     1   2                        
    / \                                                   
   1   2                                

输出:true

解析:

​ 本题是101 对称二叉树的变种题,解题分为两个步骤,第一步遍历 root 树找和 subRoot 相同的根节点,第二步判断 root 中子树是否和 subRoot 相同。

​ 判断两颗二叉树是否相同和判断二叉树是否对称思路一致,递归对比参与比较的两个节点值,最终递归将节点全部顺利比较完成则两颗二叉树相同,否在有一棵树先被遍历完成或者出现节点值不相同的情况,那么这两颗树也不相同。

​ 遍历二叉树寻找相同子树的过程就是递归遍历每一颗子树,遍历过程中不断与 subRoot 进行比较得出结果。

public:
    bool isSameTree(TreeNode* root, TreeNode* subRoot){
        if(!root && !subRoot){
            return true;
        }else if(!root || !subRoot){
            return false;
        }else if(root->val!=subRoot->val){
            return false;
        }
        return isSameTree(root->left,subRoot->left) && isSameTree(root->right,subRoot->right);
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(!subRoot){
            return true;
        }else if(!root){
            return false;
        }
        return isSameTree(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
    }
};

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

404 左叶子之和

给定一个二叉树,计算该树的所有左叶子之和

输入一颗二叉树,输出一个整数表示所有左叶子之和

输入:

 3
/ \
9  20
/  \
15   7

输出:24
解释:在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

解析:

​ 本题的关键就在于利用左叶子节点的定义进行有条件递归遍历二叉树,同时要判断一个节点是不是叶子节点,定义一个辅助函数如果该节点没有子节点则说明该节点是叶子节点。

​ 如果一个节点是左叶子节点,那么它是某个节点的左子节点,并且它还是一个叶子结点。

​ 根据此定义,在递归遍历过程中,如果一个节点有左子节点,且该节点是一个叶子节点,那么将该左子节点加到累和中;假若该左子节点不是叶子节点,则以该左子节点为根节点递归查找左叶子节点。

​ 如果一个节点有右子节点,且该节点是一个叶子节点,不进行累和且终止往下递归;假若该右子节点不是叶子节点,则将该右子节点为根节点递归查找左叶子节点。

class Solution {
public:
    bool isLeafNode(TreeNode* root){
        return  !root->left && !root->right;
    }

    int sumOfLeftLeaves(TreeNode* root) {
        if(!root){
            return 0;
        }
        int ans = 0;
        if(root->left){
            ans += isLeafNode(root->left)?root->left->val:sumOfLeftLeaves(root->left);
        }
        if(root->right){
            ans += isLeafNode(root->right)?0:sumOfLeftLeaves(root->right);
        }
        return ans;
    }
};

437 路径总和 III

给定一个整数二叉树,求有多少条路径节点值的和等于给定值。

输入一个二叉树和一个给定整数,输出一个整数,表示有多少条满足条件的路径。

输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出:3

解析:

​ 本题的关键在于计算路径和,所以在递归每个节点时,需要分情况考虑:

  • 如果选取该节点加入路径,则之后必须继续加入连续节点,或停止加入节点
  • 如果不选取该节点加入路径,则对其左右节点进行重新进行考虑

​ 因此一个方便的方法是创建一个辅函数,专门用来计算连续加入节点的路径。该辅助函数就是通过用给定值递归减去路径节点值,最终给定值减为0表示构成一条路径。

class Solution {
public:
    int pathWithRoot(TreeNode* root, int sum){
        if(!root){
            return 0;
        }
        int count = 0;
        // 如果当前节点值与路径和一致则形成一条路径
        if(root->val == sum){
            count = 1;
        }else{
            count = 0;
        }
        // 往左右子节点继续寻找路径
        count += pathWithRoot(root->left, sum-root->val);
        count += pathWithRoot(root->right, sum-root->val);
        return count;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if(!root){
            return 0;
        }
        // 将当前节点加入路径
        int ans = 0;
        ans = pathWithRoot(root,targetSum);
        // 不将当前节点加入路径,从左右子节点开始寻找新路径
        ans += pathSum(root->left,targetSum);
        ans += pathSum(root->right,targetSum);
        return ans;
    }
};

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 章 指针三剑客之树

发表评论:

Copyright Your WebSite.Some Rights Reserved.