971.翻转二叉树以匹配先序遍历

链接：971.翻转二叉树以匹配先序遍历
难度：Medium
标签：树、深度优先搜索、二叉树
简介：请翻转 最少 的树中节点，使二叉树的 先序遍历 与预期的遍历行程 voyage 相匹配 。 。

题解 1 - typescript

• 编辑时间：2021-08-14
• 执行用时：84ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：dfs。

function flipMatchVoyage(root: TreeNode | null, voyage: number[]): number[] {
  if (root === null) return [];
  const ans: number[] = [];
  let stop = false;
  dfs(root, voyage);
  return stop ? [-1] : ans;
  function dfs(node: TreeNode, voyage: number[]) {
    if (stop) return;
    const val = node.val;
    const n = voyage.length;
    if (val !== voyage[0]) {
      stop = true;
      return;
    }
    if (node.left === null && node.right === null) {
      if (!(n === 1 && voyage[0] === val)) stop = true;
      return;
    }
    if (node.left === null) {
      if (voyage[1] !== node.right!.val) stop = true;
      else dfs(node.right!, voyage.slice(1));
      return;
    }
    if (node.right === null) {
      if (voyage[1] !== node.left!.val) stop = true;
      else dfs(node.left!, voyage.slice(1));
      return;
    }
    const valL = node.left!.val;
    const valR = node.right!.val;
    if (voyage[1] === valL) {
      let idx = 1;
      while (idx < n && voyage[idx] !== valR) idx++;
      dfs(node.left!, voyage.slice(1, idx));
      dfs(node.right!, voyage.slice(idx));
    } else {
      let idx = 1;
      while (idx < n && voyage[idx] !== valL) idx++;
      dfs(node.right!, voyage.slice(1, idx));
      dfs(node.left!, voyage.slice(idx));
      ans.push(val);
    }
  }
}