自顶向下的状态传递

什么是自顶向下的状态传递？

• 模式: 进入节点时把父节点累积的状态带进来, 到达叶节点时收集答案;
• 适合: 路径和、根到叶拼成的数字等 "从根出发的路径" 问题;
• 配套: 需要输出路径本身的题目用回溯, 在进入时压入、退出时弹出;

路径总和能否成立如何判断？

• 目标: 是否存在一条根到叶的路径, 节点值之和等于 targetSum;
• 递推: 到达某节点时将剩余目标减去该节点的值; 叶节点处剩余目标为 0 即成立;
• 剪枝: 一侧子树返回 true 时无需继续;

const hasPathSum = function (root, targetSum) {
  const backtrack = (node, rest) => {
    if (node.left == null && node.right == null) return rest === 0;
    if (node.left != null && backtrack(node.left, rest - node.left.val)) return true;
    if (node.right != null && backtrack(node.right, rest - node.right.val)) return true;
    return false;
  };

  return root != null && backtrack(root, targetSum - root.val);
};

需要输出全部路径时怎么做？

• 区别: 维护当前路径数组 state, 命中答案时拷贝一份再收集;
• 回溯必要性: 递归返回后必须弹出当前节点, 否则路径会串到兄弟分支;

const pathSum = function (root, targetSum) {
  const res = [];
  const backtrack = (node, state) => {
    if (node.left == null && node.right == null) {
      if (state.reduce((a, b) => a + b, 0) === targetSum) res.push([...state]);
      return;
    }
    if (node.left != null) {
      state.push(node.left.val);
      backtrack(node.left, state);
      state.pop();
    }
    if (node.right != null) {
      state.push(node.right.val);
      backtrack(node.right, state);
      state.pop();
    }
  };

  if (root != null) backtrack(root, [root.val]);
  return res;
};

路径拼成数字的问题怎么做？

• 问题: 根到叶路径的每一位拼成一个数字, 求所有路径数字之和;
• 递推: sum = node.val + 10 * parentSum; 到叶节点时直接返回该数字;

const sumNumbers = function (root) {
  const dfs = (node, sum) => {
    if (node == null) return 0;
    const next = 10 * sum + node.val;
    if (node.left == null && node.right == null) return next;
    return dfs(node.left, next) + dfs(node.right, next);
  };

  return dfs(root, 0);
};

• 复杂度: 上述各题都是时间 O(n), 空间 O(n) 递归栈;