971. Flip Binary Tree To Match Preorder Traversal

Link

Solution

Traverse the node from root to it's children with DFS, once flip condition is satisfied then flip, otherwise

go the same way till the end.

   int index = 0;
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        List<Integer> ret = new LinkedList<>();
        
        return dfs(root, voyage, ret) ? ret : Arrays.asList(-1);
        
    }
    
    private boolean dfs(TreeNode node, int[] voyage, List<Integer> ret){
        
        if(node == null) return true;
        
        if(node.val != voyage[index]) return false;
        index++;
        
        if(node.left != null && node.left.val != voyage[index]){
           ret.add(node.val);
            return dfs(node.right, voyage, ret) && dfs(node.left, voyage, ret);
        }
        return dfs(node.left, voyage, ret) && dfs(node.right, voyage, ret);
        
    }