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

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

给定二叉树和目标先序遍历 voyage，可以通过翻转左右子节点使树的先序遍历匹配 voyage。返回需要翻转的节点值列表。

示例 1:

输入：root = [1,2], voyage = [2,1]
输出：[1]

提示:

• 树中节点数在 1 到 100 之间
• 节点值唯一，范围 1 到 n

解析

DFS 先序遍历，对比 voyage 数组，遇到不匹配时尝试翻转。

var flipMatchVoyage = function (root, voyage) {
  const result = [];
  let idx = 0;

  const dfs = (node) => {
    if (!node) return true;
    if (node.val !== voyage[idx++]) return false;

    if (node.left && node.right && idx < voyage.length && node.right.val === voyage[idx]) {
      result.push(node.val);
      return dfs(node.right) && dfs(node.left);
    }

    return dfs(node.left) && dfs(node.right);
  };

  const valid = dfs(root);
  return valid ? result : [-1];
};

时间复杂度 O(N)，空间复杂度 O(H)。