console 命令行工具 X clear

console

// Node定义
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}
// 根据数组生成树
function genNode(arr, i){
    let node = null
    if(arr[i] && i < arr.length){
        node = new TreeNode(arr[i])
        // console.log(i, arr.length, node)
        node.left = genNode(arr, 2 * i + 1)
        node.right = genNode(arr, 2 * i + 2)
    }
    return node
}
//测试
// let arr = [7,4,3,null,null,6,19]
// let result = genNode(arr, 0)

// 返回copy里的相同节点
var getTargetCopy = function(original, cloned, target) {
    let result = null
    if(original){
        if(original === target){
            result = cloned
        }
        if(!result){
            result = getTargetCopy(original.left, cloned.left, target)
        }
        if(!result){
            result = getTargetCopy(original.right, cloned.right, target)
        }
    }
    return result
    
};
// 根据节点值查找节点
var findByNodeVal = function(tree, val){
    let node = tree
    let find = null
    if(node){
        if(node.val == val){
            return node
        }
        find = findByNodeVal(node.left, val)
        if(find) return find
        find = findByNodeVal(node.right, val)
    }
    return find
}
//测试
// let node = findByNodeVal(result, 3)
// let target = getTargetCopy(result, result, node)
// console.log(target)

// 计算二叉搜索树给定范围的节点和
var rangeSumBST = function(root, low, high) {
    let sum = 0
    if(root){
        if(root.val < low){
            sum = rangeSumBST(root.right, low, high)
        }else if(root.val > high){
            sum = rangeSumBST(root.left, low, high)
        }else{
            sum = root.val + rangeSumBST(root.right, low, high) + rangeSumBST(root.left, low, high)
        }
    }
    return sum
};

// 测试
// let bstArr = [10,5,15,3,7,null,18]
// let bstTree = genNode(bstArr, 0);
// console.log(rangeSumBST(bstTree, 7, 15))

// 生成所有可能的二叉搜索树, n为节点的个数
var generateTrees = function(n) {
    let arr = []
    for(let i = 0; i < n; i++){
        arr.push(i+1)
    }
    return generateTreesByArr(arr)
    
};
var generateTreesByArr = function(arr){
    let result = []
    for(let i = 0; i < arr.length; i++){
        let leftTrees =  generateTreesByArr(arr.slice(0, i))
        let rightTrees = generateTreesByArr(arr.slice(i + 1))
        if(!leftTrees.length && !rightTrees.length){
            return [new TreeNode(arr[i])]
        }
        if(!leftTrees.length){
            leftTrees = [null]
        }
        if(!rightTrees.length){
            rightTrees = [null]
        }

        for(let j = 0; j < leftTrees.length; j++){
            for(let x = 0; x < rightTrees.length; x++){
                let node = new TreeNode(arr[i])
                node.left = leftTrees[j]
                node.right = rightTrees[x]
                result.push(node)
            }
        }               
    }
    return result
}
//测试
// console.log(generateTrees(8))

// 查找二叉树上的路径和
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function(root, targetSum) {
    console.log(root)
    console.log(targetSum)
    if(!root.left && !root.right){
        if(root.val === targetSum){
            return [[root.val]]
        }
        return []
    }
    if(targetSum < root.val){
        return []
    }
    let leftPaths = []
    let rightPaths = []

    if(root.left){
        let tmp = pathSum(root.left, targetSum - root.val)
        leftPaths = tmp.map((p, i)=>{
            return [root.val].concat(p)
        })
    }
    if(root.right){
        let tmp = pathSum(root.right, targetSum - root.val)
        rightPaths = tmp.map((p, i)=>{
            return [root.val].concat(p)
        })    
    }

    return leftPaths.concat(rightPaths)
};

// let arr = [5,4,8,11,null,13,4,7,2,null,null,5,1];
let arr = [1,2,3];
let root = genNode(arr, 0);
console.log(pathSum(root, 4))

<html>
    <body>
        abc
    </body>
</html>