package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/
 */
public class Problem971 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        List<Integer> answer = new ArrayList<>();
        // TODO
        return answer;
    }

    public static void main(String[] args) {
        Problem971 prob = new Problem971();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        System.out.println(prob.flipMatchVoyage(root, new int[]{2, 1})); // [-1]

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(prob.flipMatchVoyage(root, new int[]{1, 3, 2})); // [1]

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(prob.flipMatchVoyage(root, new int[]{1, 2, 3})); // []
    }
}

@@ -475,15 +475,155 @@
     
-// TODO
+boolean b = flipMatchVoyage(root, voyage, new Index(), answer);%0A        if (!b) %7B%0A            answer.clear();%0A            answer.add(-1);%0A        %7D
 %0A   
@@ -654,29 +654,30 @@
 %7D%0A%0A    p
-ublic
+rivate
  static 
 void mai
@@ -672,508 +672,751 @@
 tic 
-void main(String%5B%5D args) %7B%0A        Problem971 prob = new Problem971();%0A%0A        TreeNode root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        System.out.println(prob.flipMatchVoyage(root, new int%5B%5D%7B2, 1%7D)); // %5B-1%5D%0A%0A        root = new TreeNode(1);%0A        root.lef
+class Index %7B%0A        private int val;%0A%0A        public Index inc() %7B%0A            val++;%0A            return this;%0A        %7D%0A%0A        public Index dec() %7B%0A            val--;%0A            return this;%0A        %7D%0A    %7D%0A%0A    private static boolean flipMatchVoyage(TreeNode current, int%5B%5D voyage, Index index,%0A                                           List%3CInteger%3E answer) %7B%0A        if (curren
 t =
+=
  n
-ew TreeNode(2);%0A        root.right = new TreeNode(3);%0A        System.out.println(prob.flipMatchVoyage(root, new int%5B%5D%7B1, 3, 2%7D)); // %5B1%5D%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A
+ull) %7B%0A            index.dec();%0A            return true;%0A        %7D%0A        int val = voyage%5Bindex.val%5D;%0A        if (current.val == val) %7B%0A            boolean b = flipMatchVoyage(current.left, voyage, index.inc(), answer);%0A            if (!b) %7B%0A                TreeNode tmp = current.left;%0A                current.left = current.right;%0A       
         
 root
@@ -1411,19 +1411,23 @@
         
-roo
+ curren
 t.right 
@@ -1432,106 +1432,331 @@
 t = 
-new TreeNode(3);%0A        System.out.println(prob.flipMatchVoyage(root, new int%5B%5D%7B1, 2, 3%7D)); // %5B%5D
+tmp;%0A                b = flipMatchVoyage(current.left, voyage, index, answer);%0A                if (!b) %7B%0A                    return false;%0A                %7D%0A                answer.add(current.val);%0A            %7D%0A            return flipMatchVoyage(current.right, voyage, index.inc(), answer);%0A        %7D%0A        return false;
 %0A   

Solve problem 971