首页 > 其他 > 详细

力扣 - 814. 二叉树剪枝

时间:2020-12-19 09:22:18      阅读:33      评论:0      收藏:0      [点我收藏+]

题目

814. 二叉树剪枝

思路

  • 就是先从最后一层叶子节点开始判断,将左右子树的结果反馈给父节点,让父节点做出判断
  • 根据这个思路我们可以利用二叉树的后序遍历来实现:
    • 后序遍历就是先左孩子,然后右孩子,最后父节点
    • 父节点的判断条件就是:父节点本身的值是否为1、左孩子是否为存在1、右孩子是否存在1.这三者只要满住一个就可以了
  • 同时,在pruneTree函数中,我们返回的结果也要做一个判断,如果整颗数都是0,那么返回false,否则返回根节点root

代码

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        // 判断搜索的结果是什么,如果false就返回null,否则返回root
        return search(root) ? root : null;
    }

    private boolean search(TreeNode root) {
        if (root == null) {
            return false;
        }

        // 后序遍历
        boolean left = search(root.left);
        boolean right = search(root.right);

        if (left == false) {
            root.left = null;
        }
        if (right == false) {
            root.right = null;
        }

        return root.val == 1 || left || right;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\),其中 N 为节点的个数
  • 空间复杂度:\(O(H)\),其中 H 为树的高度

力扣 - 814. 二叉树剪枝

原文:https://www.cnblogs.com/linzedian/p/14157753.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!