记一次华子的社招面试题

算法题目

解答

采用dfs遍历树，对任意节点来说，有两种情况可以得到目标和：

1. 以它开始的路径和等于目标和
2. 以它为结束的路径和等于目标和

具体方法是保存任意节点所有子树能得到的所有路径和，与其本身的值相加后判断，记录更新后的结果，与节点本身的值一并作为运算结果回传到其父节点。

let result = 0;

class TreeNode {
    constructor(v) {
        this.v = v;
        this.left = null;
        this.right = null;
    }
}

function generateTree(arr) {
    let nodes = arr.map(v => new TreeNode(v));
    let que = [];

    que.push(0);

    while(que.length) {
        let currentIdx = que.pop();
        let currentNode = nodes[currentIdx];
        let left = 2 * currentIdx + 1;
        let right = 2 * currentIdx + 2;

        if (left < nodes.length) {
            currentNode.left = nodes[left];
            if (nodes[left]) {
                que.push(left);
            }
        }

        if (right < nodes.length) {
            currentNode.right = nodes[right];
            if (nodes[right]) {
                que.push(right);
            }
        }
    }

    return nodes[0];
}

function loop(node) {
    if (node) {
        console.log(node.v);
        loop(node.left);
        loop(node.right);
    }
}

function run(arr, target) {
    let root = generateTree(arr);
    result = 0;
    // loop(root);
    dfs(root, target);
    console.log('result', result);
}

function dfs(node, target) {
    let currentSum = node.v;
    let leftSum = 0;
    let rightSum = 0;
    let res = [];

    if (node.left !== null) {
        leftSum = dfs(node.left, target);
        for (let sum of leftSum) {
            if (sum + currentSum === target) {
                result++;
            }
            res.push(sum + currentSum);
        }
    }

    if (node.right !== null) {
        rightSum = dfs(node.right, target);
        for (let sum of rightSum) {
            if (sum + currentSum === target) {
                result++;
            }
            res.push(sum + currentSum);
        }
    }

    res.push(currentSum)

    return res;
}

// 测试运行
run([10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], 8)
run([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], 22)