814. 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.)

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


Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

题目的意思是对一个二叉树进行剪枝，参数是二叉树的根节点，返回一个新的二叉树，叶子节点不能为0。
其实剪枝算法的思路不难，分别对左右子节点进行递归，结束条件是当节点是null。从每次的递归中找到叶子节点，如果节点值不是1就返回为null。

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
31
32
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
function TreeNode(val) {
    this.val = val
    this.left = this.right = null
}
var pruneTree = function(root) {
    if(root === null){
        return null
    }
    if(root ===undefined){
        return null
    }
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)
 
    if(root.left===null && root.right===null){
        if(root.val===0){
            return null
        }
    }
    return root
};

其实题目只要求实现这个剪枝算法就可以了。为了得到相同的输入与输出，还需要根据输入构建二叉树，遍历剪枝的结果存入数组中。这个部分花了比较多的时间。
创建一个完全二叉树主要就是找到节点序号的规律，左节点序号为2i+1，右节点序号为2i+2。然后循环节点数组，给每一个节点添加左右儿子，因为是浅拷贝，所以根节点也会不断被添加儿子。注意判断一下值为null的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for(var i=0; i<test.length; i++){
    nodeList.push(new TreeNode(test[i]))
}
var index = 0
var i = 0
while (index<nodeList.length) {
    if(nodeList[index].val==null){
        index = index+1
        i=i
    }else {
        var leftindex = 2*i+1
        var rightindex = 2*i+2
        nodeList[index].left = nodeList[leftindex]
        nodeList[index].right = nodeList[rightindex]
        index = index+1
        i=i+1
    }
}
//构建树
var root = nodeList[0]

剪枝后返回二叉树的根节点，进行宽度优先遍历，把节点的val值存入输出数组中。宽度优先遍历用队列实现，把根节点放入队列，每次从队列头部弹出一个节点，并把它的左右儿子放入队列里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//宽度优先遍历 队列
var q = []
var rnode = result
var output = []
q.push(rnode)
while (q.length!=0){
    var node = q.shift()
    if(node==null) {
        output.push(null)
    }
    else {
        output.push(node.val)
        if(node.left || (node.left==null&&(node.left||node.right)) ) q.push(node.left)
        if(node.right || (node.right==null&&(node.left||node.right)) ) q.push(node.right)
    }
 
}
console.log(output)