LeetCode 971 - Flip Binary Tree To Match Preorder Traversal

https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/

Given a binary tree with N nodes, each node has a different value from {1, ..., N}.

A node in this binary tree can be flipped by swapping the left child and the right child of that node.

Consider the sequence of N values reported by a preorder traversal starting from the root.  Call such a sequence of N values the voyage of the tree.

(Recall that a preorder traversal of a node means we report the current node's value, then preorder-traverse the left child, then preorder-traverse the right child.)

Our goal is to flip the least number of nodes in the tree so that the voyage of the tree matches the voyage we are given.

If we can do so, then return a list of the values of all nodes flipped.  You may return the answer in any order.

If we cannot do so, then return the list [-1].

Example 1:

Input: root = [1,2], voyage = [2,1]
Output: [-1]

Example 2:

Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]

Example 3:

Input: root = [1,2,3], voyage = [1,2,3]
Output: []

Note:

1. 1 <= N <= 100

https://blog.csdn.net/fuxuemingzhu/article/details/85939252
其实这个题不难，因为题目就说了是前序遍历，所以做法肯定还是前序遍历。我刚开始一直想不通的地方在于，题目又是返回[-1]，又是正常返回，没想好怎么做区分。其实做法就是递归函数不仅要修改res数组，还要返回表示能不能构成题目条件的bool变量。

按照lee215的说法，看到二叉树的题，很大可能就需要递归，所以直接先写出dfs函数，然后再慢慢向里面填东西。

我们定义的dfs函数意义是，我们能不能通过翻转（或者不翻转）该root节点的左右子树，得到对应v。如果能，返回true，否则返回false。

首先在递归函数中，我们对root节点进行判断，如果root不存在，这种情况不应该认为是题目输入错误，而是应该认为已经遍历到最底部了，这个时候相当于root = [], voyage = []，所以返回true;在先序遍历的时候，root节点是第一个要被遍历到的节点，如果不和voyage[0]相等，直接返回false;

这个题目的难点在于是否需要翻转一个节点的左右孩子。判断的方法其实是简单的：如果voyage第二个元素等于root的左孩子，那么说明不用翻转，直接递归调用左右孩子；否则如果voyage的第二个元素等于root的右孩子，那么还要注意一下，在左孩子存在的情况下，我们需要翻转当前的节点左右孩子。

翻转是什么概念呢？这里并没有直接交换，而是把当前遍历到的位置使用遍历i保存起来，这样voyage[i]就表示当前遍历到哪个位置了。所以dfs调用两个孩子的顺序很讲究，它体现了先序遍历先解决哪个树的问题，也就是完成了逻辑上的交换左右孩子。
https://zhanghuimeng.github.io/post/leetcode-971-flip-binary-tree-to-match-preorder-traversal/

接下来的问题就是要不要翻转。如果有左子结点，那么下一个值必然是左子结点的值；否则，如果有右子结点，下一个值必然是右子结点的值；否则（也就是说没有子结点），下一个值和之前的遍历相关，可能是父节点的右子结点之类的。

所以做出翻转的决策就很简单：如果左子结点有值，且这个值和遍历序列中预期的下一个值不等，那么就交换左右子树（显然不交换肯定不行了）。判断是否可行的方法也很简单，在上述翻转的基础上，每次都判断当前根结点的值和遍历序列中预期的值是否相等。

---

事实上，这个判断左子结点的方法是题解[1]里给出的。我比赛的时候用的是，判断是否有右子结点，如果有的话，它的值如果和预期的下一个值相等，才有可能有必要进行交换（当然也有可能根本实现不了）。这个判断本质上和上述方法是一样的。

X.
https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/discuss/214216/JavaC%2B%2BPython-DFS-Solution

Global integer i indicates next index in voyage v.
If current node == null, it's fine, we return true
If current node.val != v[i], doesn't match wanted value, return false
If left child exist but don't have wanted value, flip it with right child.

    List<Integer> res = new ArrayList<>();
    int i = 0;
    public List<Integer> flipMatchVoyage(TreeNode root, int[] v) {
        return dfs(root, v) ? res : Arrays.asList(-1);
    }

    public Boolean dfs(TreeNode node, int[] v) {
        if (node == null) return true;
        if (node.val != v[i++]) return false;
        if (node.left != null && node.left.val != v[i]) {
            res.add(node.val);
            return dfs(node.right, v) && dfs(node.left, v);
        }
        return dfs(node.left, v) && dfs(node.right, v);
    }

https://blog.csdn.net/fly_yr/article/details/86154745
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        List<Integer> flipPath = new ArrayList<>();
        int resultIdx = dfs(root, 0, flipPath, voyage);
     
        if (resultIdx == -1 || resultIdx < voyage.length-1) {
            return Arrays.asList(-1);
        }
        return flipPath;
    }

    public int dfs(TreeNode root, int idx, List<Integer> flipPath, int[] voyage) {
        if (root == null) {
            return idx;
        }
     
        if (idx >= voyage.length) {
            return -1;
        }

        if(root.val != voyage[idx]) {
            return -1;
        }

        int left = dfs(root.left, idx + 1, flipPath, voyage);
        if (left != -1) {
            //Completed the leaf node in left child, then right child
            return dfs(root.right, left, flipPath, voyage);
        }

        //Need to flip
        flipPath.add(root.val);

        int right = dfs(root.right, idx + 1, flipPath, voyage);
        if (right != -1) {
            return dfs(root.left, right, flipPath, voyage);
        }

        return -1;
    }
https://www.acwing.com/solution/LeetCode/content/755/
    bool dfs(TreeNode *rt, const vector<int>& voyage, int& cur, vector<int>& ans) {
        if (rt == nullptr)
            return true;

        if (rt -> val != voyage[cur])
            return false;

        cur++;

        if (dfs(rt -> left, voyage, cur, ans) && dfs(rt -> right, voyage, cur, ans))
            return true;

        if (dfs(rt -> right, voyage, cur, ans) && dfs(rt -> left, voyage, cur, ans)) {
            ans.push_back(rt -> val);
            return true;
        }

        return false;
    }

    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
        int cur = 0;
        vector<int> ans;

        if (!dfs(root, voyage, cur, ans))
            return {-1};

        return ans;
    }
https://leetcode.com/articles/flip-binary-tree-to-match-preorder-traversal/
Approach 1: Depth-First Search

As we do a pre-order traversal, we will flip nodes on the fly to try to match our voyage with the given one.

If we are expecting the next integer in our voyage to be voyage[i], then there is only at most one choice for path to take, as all nodes have different values.

Do a depth first search. If at any node, the node's value doesn't match the voyage, the answer is [-1].

Otherwise, we know when to flip: the next number we are expecting in the voyage voyage[i] is different from the next child.

  List<Integer> flipped;

  int index;

  int[] voyage;

  public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {

    flipped = new ArrayList();

    index = 0;

    this.voyage = voyage;

    dfs(root);

    if (!flipped.isEmpty() && flipped.get(0) == -1) {

      flipped.clear();

      flipped.add(-1);

    }

    return flipped;

  }

  public void dfs(TreeNode node) {

    if (node != null) {

      if (node.val != voyage[index++]) {

        flipped.clear();

        flipped.add(-1);

        return;

      }

      if (index < voyage.length && node.left != null && node.left.val != voyage[index]) {

        flipped.add(node.val);

        dfs(node.right);

        dfs(node.left);

      } else {

        dfs(node.left);

        dfs(node.right);

      }

    }

  }

X.

https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/discuss/214219/Java-DFS-try-the-only-way

1. Input i of dfs() is the current index in voyage, then root.val == voyage[i], otherwise return -1.
2. The return of dfs() is the index in voyage for the successor of preorder traversal.

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        List<Integer> path = new ArrayList<>();
        if (dfs(root, voyage, 0, path) == -1) {
            List<Integer> result = new ArrayList<>();
            result.add(-1);
            return result;
        }
        return path;
    }
    private int dfs(TreeNode root, int[] voyage, int i, List<Integer> path) {
        if (root == null) {
            return i;
        }
        if (root.val != voyage[i]) {
            return -1;
        }
        int left = dfs(root.left, voyage, i + 1, path);
        if (left != -1) {
            return dfs(root.right, voyage, left, path);
        }
  // need a flip
        path.add(root.val);
        int right = dfs(root.right, voyage, i + 1, path);
        if (right != -1) {
            return dfs(root.left, voyage, right, path);
        }
        return -1;
    }

https://blog.csdn.net/fuxuemingzhu/article/details/85939252
其实这个题不难，因为题目就说了是前序遍历，所以做法肯定还是前序遍历。我刚开始一直想不通的地方在于，题目又是返回[-1]，又是正常返回，没想好怎么做区分。其实做法就是递归函数不仅要修改res数组，还要返回表示能不能构成题目条件的bool变量。

按照lee215的说法，看到二叉树的题，很大可能就需要递归，所以直接先写出dfs函数，然后再慢慢向里面填东西。

我们定义的dfs函数意义是，我们能不能通过翻转（或者不翻转）该root节点的左右子树，得到对应v。如果能，返回true，否则返回false。

首先在递归函数中，我们对root节点进行判断，如果root不存在，这种情况不应该认为是题目输入错误，而是应该认为已经遍历到最底部了，这个时候相当于root = [], voyage = []，所以返回true;在先序遍历的时候，root节点是第一个要被遍历到的节点，如果不和voyage[0]相等，直接返回false;

这个题目的难点在于是否需要翻转一个节点的左右孩子。判断的方法其实是简单的：如果voyage第二个元素等于root的左孩子，那么说明不用翻转，直接递归调用左右孩子；否则如果voyage的第二个元素等于root的右孩子，那么还要注意一下，在左孩子存在的情况下，我们需要翻转当前的节点左右孩子。

翻转是什么概念呢？这里并没有直接交换，而是把当前遍历到的位置使用遍历i保存起来，这样voyage[i]就表示当前遍历到哪个位置了。所以dfs调用两个孩子的顺序很讲究，它体现了先序遍历先解决哪个树的问题，也就是完成了逻辑上的交换左右孩子。

https://medium.com/@poitevinpm/solution-to-leetcode-problem-971-flip-binary-tree-to-match-preorder-traversal-bea0124e7f8c
- No need to change the tree

  public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {

    List<Integer> result = new ArrayList<>();

    if (helper(root, voyage, result, new int[] { -1 }, null))

      return result;

    result.clear();

    result.add(-1);

    return result;

  }

  public boolean helper(TreeNode root, int[] voyage, List<Integer> result, int[] index, TreeNode prev) {

    if (root == null)

      return true;

    int k = ++index[0];

    if (root.val != voyage[k])

      return false;

    if (root.left != null) {

      if (k + 1 >= voyage.length) //

        return false;

      if (root.left.val != voyage[k + 1]) {

        result.add(k + 1);

        TreeNode tmp = root.left;

        root.left = root.right;

        root.right = tmp;

      }

      if (!helper(root.left, voyage, result, index, root))

        return false;

    }

    return helper(root.right, voyage, result, index, root);

  }

X. Stack
https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/discuss/214384/JavaC%2B%2BPython-Iterative-Solution-Using-Stack

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        List<Integer> res = new ArrayList<>();
        int i = 0;
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while (s.size() > 0) {
            TreeNode node = s.pop();
            if (node == null) continue;
            if (node.val != voyage[i++]) return Arrays.asList(-1);
            if (node.right != null && node.right.val == voyage[i]) {
                if (node.left != null) res.add(node.val);
                s.push(node.left);
                s.push(node.right);
            } else {
                s.push(node.right);
                s.push(node.left);
            }
        }
        return res;
    }