leetcode题解-814-二叉树剪枝

发表于 | 更新于

题目

官方way

递归

java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        return containsOne(root) ? root : null;
    }

    public boolean containsOne(TreeNode node) {
        if (node == null) return false;
        boolean a1 = containsOne(node.left);
        boolean a2 = containsOne(node.right);
        if (!a1) node.left = null;
        if (!a2) node.right = null;
        return node.val == 1 || a1 || a2;
    }
}
C++实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    bool helper(TreeNode* root)
    {
        if (!root)  return false;

        bool lDel = helper(root->left);
        bool lRig = helper(root->right);

        if (!lDel)  root->left = nullptr;
        if (!lRig)  root->right = nullptr;

        return root->val == 1 | lDel | lRig;
    }

public:
    TreeNode* pruneTree(TreeNode* root) 
    {
        return helper(root) ? root : nullptr;
    }
};

总结

  • 自己一开始的递归思路不合理。
  • 递归终止条件： 到达nullptr处，return false
  • 递归状态：
    1. 当前结点值 == 1
    2. 左子树 == 全为1
    3. 右子树 == 全为1

Reference

https://leetcode-cn.com/problems/binary-tree-pruning/solution/er-cha-shu-jian-zhi-by-leetcode/