[leetcode] Binary Tree Pruning

发布时间：2020-12-14 03:21:39 所属栏目：大数据来源：网络整理

导读：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

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

Example 3:

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

Note:

The binary tree?will?have?at?most?100 nodes.
The value of each node will only be?0?or?1.

分析：这个题目的关键是找到如何判断子树全是0。很自然的想到用DFS函数去深度遍历，并且DFS应该设置为boolean类型，递归终止的条件是root==null，如果某个node，node.left==null，node.right==null并且node.val=0，那么就把这个node设为null。代码如下：

 1 class Solution {
 2     public TreeNode pruneTree(TreeNode root) {
 3         dfs(root);
 4         return root;
 5     }
 6     private boolean dfs(TreeNode root){
 7         //下面的代码完成对叶子节点的判断
 8         if ( root == null ) return true;
 9         boolean left = dfs(root.left);
10         boolean right = dfs(root.right);
11         if ( left && right && root.val == 0 ) return true;
12         
13         //下面的代码完成对叶子节点父节点的操作
14         if ( left ) root.left=null;
15         if ( right ) root.right=null;
16         
17         //如果叶子节点不满足上面的条件，就返回false
18         return false;
19     }
20 }

? ? ? 从上面的代码可以清晰的看到DFS的三层架构，第一层要对当前节点进行判断，也就是递归结束的标志；第二层是操作层，当条件满足时要进行的操作；第三层就是当当前节点条件不满足时返回值。要注意在深度搜索中，都是从叶子节点向上搜索。

? ? ? 运行时间1ms，深搜确实是面对Tree问题的第一选择。

第二种思路，参考了其他人提交的代码，也可以优化第一种方法，不用boolean记录每个节点的情况。反而可读性更强，代码如下：

 1 class Solution {
 2     public TreeNode pruneTree(TreeNode root) {
 3         return helper(root);
 4     }
 5     private TreeNode helper(TreeNode root) {
 6         if ( root == null ) return null;
 7         root.left = helper(root.left);
 8         root.right = helper(root.right);
 9         if ( root.left == null && root.right == null && root.val == 0 ) return null;
10         return root;
11     }
12 }

? ? ? 同样的1ms时间，这个代码可读性更强，更好理解。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!