[LintCode/LeetCode] Binary Tree Pruning

rockswang 发布于2019-08-16 12:37 / 3380人阅读

Problem

Binary Tree Pruning
We are given the head node root of a binary tree, where additionally every node"s value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example

Example 1:
Input: [1,#,0,0,1]
Output: [1,#,0,#,1]

Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,#,1,#,1]

Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,#,1]

Solution

public class Solution {
    /**
     * @param root: the root
     * @return: the same tree where every subtree (of the given tree) not containing a 1 has been removed
     */
    public TreeNode pruneTree(TreeNode root) {
        // Write your code here
        if (root == null) return null;
        if (root.val == 0 && root.left == null && root.right == null) return null;
        if (isValid(root.left)) {
            root.left = pruneTree(root.left);
        } else root.left = null;
        if (isValid(root.right)) {
            root.right = pruneTree(root.right);
        } else root.right = null;
        return root;
    }
    private boolean isValid(TreeNode node) {
        if (node == null) return false;
        if (node.val == 1 || isValid(node.left) ||isValid(node.right)) return true;
        else return false;
    }
}

GPU服务器海外云主机 binary-tree binary-search-tree Pruning Binary

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71400.html

[LintCode/LeetCode] Balanced Binary Tree

摘要：根据二叉平衡树的定义，我们先写一个求二叉树最大深度的函数。在主函数中，利用比较左右子树的差值来判断当前结点的平衡性，如果不满足则返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...

morgan 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Construct Binary Tree from Tr

摘要：做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。这道题目的要点在于找的区间。边界条件需要注意若或数组为空，返回空当前进到超出末位，或超过，返回空每次创建完根节点之后，要将加，才能进行递归。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

马忠志 2019-08-14 15:40 评论0 收藏0
[LintCode/LeetCode] Binary Tree Maximum Path Sum

摘要：调用函数更新路径和的最大值，而函数本身需要递归，返回的是单边路径和。所以函数要返回的是，主函数中返回的却是最上一层根节点处和的较大值，与之前遍历过所有路径的最大值之间的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...

cnTomato 2019-08-14 15:34 评论0 收藏0
[LintCode/LeetCode] Binary Tree Zigzag Level Orde

Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...

AlphaGooo 2019-08-14 15:40 评论0 收藏0
[LintCode/LeetCode] Binary Tree InOrder Traversal

摘要：递归法不说了，栈迭代的函数是利用的原理，从根节点到最底层的左子树，依次入堆栈。然后将出的结点值存入数组，并对出的结点的右子树用函数继续迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...

tomorrowwu 2019-08-14 15:39 评论0 收藏0