資訊專欄INFORMATION COLUMN
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.)
ExampleExample 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]
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/71400.html
摘要：根據(jù)二叉平衡樹(shù)的定義，我們先寫(xiě)一個(gè)求二叉樹(shù)最大深度的函數(shù)。在主函數(shù)中，利用比較左右子樹(shù)的差值來(lái)判斷當(dāng)前結(jié)點(diǎn)的平衡性，如果不滿足則返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...
摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點(diǎn)在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進(jìn)到超出末位，或超過(guò)，返回空每次創(chuàng)建完根節(jié)點(diǎn)之后，要將加，才能進(jìn)行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...
摘要：調(diào)用函數(shù)更新路徑和的最大值，而函數(shù)本身需要遞歸，返回的是單邊路徑和。所以函數(shù)要返回的是，主函數(shù)中返回的卻是最上一層根節(jié)點(diǎn)處和的較大值，與之前遍歷過(guò)所有路徑的最大值之間的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...
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...
摘要：遞歸法不說(shuō)了，棧迭代的函數(shù)是利用的原理，從根節(jié)點(diǎn)到最底層的左子樹(shù)，依次入堆棧。然后將出的結(jié)點(diǎn)值存入數(shù)組，并對(duì)出的結(jié)點(diǎn)的右子樹(shù)用函數(shù)繼續(xù)迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...
閱讀 964·2023-04-25 23:54
閱讀 3047·2021-11-08 13:21
閱讀 3775·2021-09-27 13:35
閱讀 3391·2021-07-26 23:41
閱讀 1055·2019-08-30 15:52
閱讀 3439·2019-08-30 11:27
閱讀 2097·2019-08-29 18:37
閱讀 537·2019-08-29 17:24
