[LeetCode] 814. Binary Tree Pruning

yedf 發布于2019-08-16 13:33 / 2338人閱讀

Problem

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 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,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,null,1,null,1]

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

Solution

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0) return null;
        return root;
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree Pruning LeetCode

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71931.html

[LintCode/LeetCode] Binary Tree Pruning

Problem Binary Tree PruningWe are given the head node root of a binary tree, where additionally every nodes value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not...

rockswang 2019-08-16 12:37 評論0 收藏0
LeetCode 606. Construct String from Binary Tree 二叉

摘要：題意從一顆二叉樹轉為帶括號的字符串。這題是的姊妹題型，該題目的解法在這里解法。 LeetCode 606. Construct String from Binary Tree You need to construct a string consists of parenthesis and integers from a binary tree with the preorder t...

mikyou 2019-08-16 13:31 評論0 收藏0
LeetCode 536. Construct Binary Tree from String 從帶

摘要：題意從一個帶括號的字符串，構建一顆二叉樹。其中當而時，展示為一個空的括號。同時要考慮負數的情況，所以在取數字的時候，必須注意所在位置。遇到則從棧中出元素。最后中的元素就是，返回棧頂元素即可。 LeetCode 536. Construct Binary Tree from String You need to construct a binary tree from a string ...

tabalt 2019-08-16 13:31 評論0 收藏0
LeetCode 110 Balanced Binary Tree 平衡二叉樹

摘要：題意判斷一顆二叉樹是否是平衡二叉樹，平衡二叉樹的定義為，每個節點的左右子樹深度相差小于這是和求最大深度的結合在一起，可以考慮寫個函數找到拿到左右子樹的深度，然后遞歸調用函數判斷左右子樹是否也是平衡的，得到最終的結果。 LeetCode 110 Balanced Binary Tree Given a binary tree, determine if it is height-bala...

anquan 2019-08-16 13:28 評論0 收藏0
[LeetCode-Tree]Binary Tree Inorder & Preorder

摘要：代碼解題思路先序遍歷，同樣用迭代實現，借助棧。先將根節點入棧先序遍歷，所以直接出根節點因為順序是根，左節點，右節點，所以我們在壓棧的時候要先壓右節點，再壓左節點。所以我們自定義了一個類，添加了的屬性，來表明該節點是否已經被訪問過了。 Binary Tree Inorder TraversalGiven a binary tree, return the inorder traversa...

taowen 2019-08-16 10:26 評論0 收藏0