[LeetCode] 814. Binary Tree Pruning

yedf 發(fā)布于2019-08-16 13:33 / 2366人閱讀

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云服務(wù)器云服務(wù)器 binary-tree binary-search-tree Pruning LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71931.html

相關(guān)文章

[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 評(píng)論0 收藏0
LeetCode 606. Construct String from Binary Tree 二叉

摘要：題意從一顆二叉樹轉(zhuǎn)為帶括號(hào)的字符串。這題是的姊妹題型，該題目的解法在這里解法。 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 評(píng)論0 收藏0
LeetCode 536. Construct Binary Tree from String 從帶

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

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

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

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

摘要：代碼解題思路先序遍歷，同樣用迭代實(shí)現(xiàn)，借助棧。先將根節(jié)點(diǎn)入棧先序遍歷，所以直接出根節(jié)點(diǎn)因?yàn)轫樞蚴歉?，左?jié)點(diǎn)，右節(jié)點(diǎn)，所以我們在壓棧的時(shí)候要先壓右節(jié)點(diǎn)，再壓左節(jié)點(diǎn)。所以我們自定義了一個(gè)類，添加了的屬性，來表明該節(jié)點(diǎn)是否已經(jīng)被訪問過了。 Binary Tree Inorder TraversalGiven a binary tree, return the inorder traversa...

taowen 2019-08-16 10:26 評(píng)論0 收藏0