814. 二叉树剪枝

发表于 | 分类于
关于虚拟节点的练习

用时：6min

很简单，中序遍历，计算两边子树是否存在 1 的值，没有就去掉。凡事左右子树或者自身包含 1 ，返回 true 。否则返回 false

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
var pruneTree = function(root) {
    var DFS = function (root) {
        if (!root) return false
        var left = DFS(root.left)
        var right = DFS(root.right)
        if (!left) {
            root.left = null
        }
        if (!right) {
            root.right = null
        }
        if (left) {
            return true
        }
        if (right) {
            return true
        }
        if( root.val === 1) {
            return true
        }
    }
    var dummp = new TreeNode(1)
    dummp.left = root
    DFS(dummp)
    return dummp.left
};

一个需要注意的点是，root本身也有可能需要剪掉，所以增加了一个虚拟节点来作为父节点