『LeetCode|每日一题』----＞二叉树剪枝

目录

1.每日一句

2.作者简介

 『LeetCode|每日一题』二叉树剪枝

1.每日一题

2.解题思路

        2.1 思路分析

        2.2 核心代码（DFS）

        2.3 完整代码

        2.4 运行结果

---

1.每日一句

唯愿你我有这样的勇气，不悲伤，不犹豫，不彷徨

2.作者简介

🏡个人主页：XiaoXiaoChen-2716 

📚学习专栏：力扣专栏 

🕒发布日期：2022/10/27

 『LeetCode|每日一题』二叉树剪枝

1.每日一题

原文链接--->点我

2.解题思路

        2.1 思路分析

对于多余的枝叶，首先要从深的地方往头节点剪枝，所以用dfs正合适

        S1：首先特殊情况处理，如果根节点都是空的就没必要剪枝了；

        S2：dfs函数中只需要一个节点传进去就可以了，首先遍历到最底层的节点，往上剪枝，此时分左右两种情况：

1. 对于左子树，如果该节点的左节点不为空并且它的值为0，同时它的左节点的左节点和左节点的右节点都为空，那么此时就需要剪掉这个节点的左节点；
2. 对于右子树，同样的道理，如果该节点的右节点不为空并且值为0，同时它的右节点的左节点和右节点的右节点为空，此时该节点的右节点同样要被剪掉；

        S3：对于dfs(root.left)和dfs(root.right)必须放在剪枝的前面，因为要从深层开始剪枝

        2.2 核心代码（DFS）

    private void dfs(TreeNode root){
        if(root == null){
            return ;
        }
        dfs(root.left);
        dfs(root.right);
        if(root.left != null && root.left.val == 0 && root.left.left == null && root.left.right == null){
            root.left = null;
        }
        if(root.right != null && root.right.val == 0 && root.right.left == null && root.right.right == null){
            root.right = null;
        }
        
    }

        2.3 完整代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) return null;
        dfs(root);
        if(root.val == 0 && root.left == null && root.right == null){
            root = null;
        }
        return root;
    }
    private void dfs(TreeNode root){
        if(root == null){
            return ;
        }
        dfs(root.left);
        dfs(root.right);
        if(root.left != null && root.left.val == 0 && root.left.left == null && root.left.right == null){
            root.left = null;
        }
        if(root.right != null && root.right.val == 0 && root.right.left == null && root.right.right == null){
            root.right = null;
        }
        
    }
}

        2.4 运行结果

---

🍁 类似题目推荐：

1.数据结构基础 

2.算法专项练习 

3.剑指offer专项练习

4.推荐一个学习网站：LeetCode，算法的提升在于日积月累，只有每天练习才能保持良好的状态

如果文章对各位大佬有帮助就支持一下噢，不好的地方请各位大佬多多指教！