[LintCode/LeetCode] Binary Tree Pruning

rockswang 發布于2019-08-16 12:37 / 3465人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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