刷题（树相关leetcode3）_leetcode3 0题

129.求根到叶子节点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

思路：遍历出来每一条路径，然后变成数字相加

var sumNumbers = function(root) {
    if(root==null) return 0;
    var res=[];
    function dfs(arr,root){
        if(root.left==null&&root.right==null){
            res.push(arr.concat(root.val));
        }
        if(root.left){
            dfs(arr.concat(root.val),root.left);
        }
        if(root.right){
            dfs(arr.concat(root.val),root.right);
        }
    }
    dfs([],root);
    var sum=0;
    for(var i=0;i<res.length;i++){
        sum+=Number(res[i].join(""));
    }
    return sum;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

144.二叉树的前序遍历

思路：遍历根节点，前序遍历左子树，前序遍历右子树

var preorderTraversal = function(root) {
    if(root==null) return [];
    var arr=[];
    dfs(arr,root);
    function dfs(arr,root){
        arr.push(root.val);
        if(root.left){
            dfs(arr,root.left);
        }
        if(root.right){
            dfs(arr,root.right);
        }
    }
    return arr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

145.二叉树的后续遍历

var postorderTraversal = function(root) {
    if(root==null) return [];
    var arr=[];
    dfs(arr,root);
    function dfs(arr,root){
        arr.push(root.val);
        if(root.right){
            dfs(arr,root.right);
        }
        if(root.left){
            dfs(arr,root.left);
        }
    }
    return arr.reverse();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

814.二叉树剪枝

给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。

返回移除了所有不包含 1 的子树的原二叉树。

( 节点 X 的子树为 X 本身，以及所有 X 的后代。)

思路：遍历左子树和右子树，判断叶子节点是否为0，如果为0，就设置为null

var pruneTree = function(root) {
    if(root==null) return null;
    root.left=pruneTree(root.left);
    root.right=pruneTree(root.right);
    if(root.left==null&&root.right==null&&root.val==0)
        return null;
    return root;
};
1
2
3
4
5
6
7
8

671. 二叉树中第二小的节点
     给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

思路：将所有节点放入数组中，排序去重，选第二个较小的

var findSecondMinimumValue = function(root) {
    if(root==null) return -1;
    if(root&&root.left==null&&root.right==null) return -1;
    function dfs(arr,root){
        arr.push(root.val);
        if(root.left){
            dfs(arr,root.left);
        }   
        if(root.right){
            dfs(arr,root.right);
        }
    }
    var arr=[];
    dfs(arr,root);
    arr=[...new Set(arr.sort((a,b)=>a-b))]
    if(arr.length==1) return -1;
    return arr[1];    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18