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 <= N <= 100

题目理解：

定义flip操作：将某一个节点root的左子树和右子树交换。给定一棵二叉树和一个先序遍历序列，如果能够使用有限次flip操作使得二叉树的先序遍历结果与给定序列相同，返回最少的flip操作序列。如果不能，返回-1。

解题思路：

先序遍历的第一个值一定是root的值，这一点对于二叉树本身和二叉树的左右子树都是一样的。因此可以在原始的先序遍历序列中，找到左右子树的先序遍历序列，找到之后递归进行判断即可。

如果先序遍历序列的第一个值与root值不相等，则不能在有限次flip达到执行先序遍历序列。

需要注意的是在没有左子树或者右子树的时候不需要进行flip操作，因为不会改变先序遍历结果。

如果进行flip操作，那么原始先序遍历的第二个值是root节点右子树的值，这时记录root节点的值即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    List<Integer> res = new ArrayList<Integer>();
    int[] voyage;
    boolean flag = true;
    
    public void dfs(TreeNode root, int left, int right){
        if(!flag)
            return;
        if(root.left == null && root.right == null){
            if(right - left > 0){
                flag = false;
                return;
            }
        }
        else if(root.left != null && root.right == null){
            if(right - left < 1 || voyage[left + 1] != root.left.val){
                flag = false;
                return;
            }
            dfs(root.left, left + 1, right);
        }
        else if(root.left == null && root.right != null){
            if(right - left < 1 || voyage[left + 1] != root.right.val){
                flag = false;
                return;
            }
            dfs(root.right, left + 1, right);
        }
        else{
            if(right - left < 2){
                flag = false;
                return;
            }
            if(voyage[left + 1] == root.left.val){
                int pos = left + 2;
                while(pos <= right && voyage[pos] != root.right.val)
                    pos++;
                if(pos > right){
                    flag = false;
                    return;
                }
                dfs(root.left, left + 1, pos - 1);
                dfs(root.right, pos, right);
            }
            else if(voyage[left + 1] == root.right.val){
                int pos = left + 2;
                while(pos <= right && voyage[pos] != root.left.val)
                    pos++;
                if(pos > right){
                    flag = false;
                    return;
                }
                res.add(root.val);
                dfs(root.right, left + 1, pos - 1);
                dfs(root.left, pos, right);
            }
            else{
                flag = false;
            }
        }
    }
    
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        this.voyage = voyage;
        if(root.val != voyage[0])
            flag = false;
        dfs(root, 0, voyage.length - 1);
        if(!flag){
            res = new ArrayList<Integer>();
            res.add(-1);
            return res;
        }
        return res;
    }
}

Flip Binary Tree To Match Preorder Traversal

相关推荐