Flip Binary Tree To Match Preorder Traversal
update Jan 8 2019, 23:19
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
Basic Idea:
维持一个全局变量curr，标示下一个要遍历的 voyage 中的index。每次我们检查当前node的值和curr对应的是否相等，如果相等，我们就递归继续判断(先左后右)，如果不相等，我们就进行一次反转，相当于先判断right再判断left(如果反转之后还不相等，则返回false)。
之所以这样的方法是对的，是因为题目规定每个node的val是unique的，这样当我们发现node.left.val == nextPreorderVal 的时候，就可以放心进入下一层递归。
Java Code:
class Solution {
private int curr = 0;
private List<Integer> res = new ArrayList<>();
public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
if (helper(root, voyage)) return res;
else {
res = new ArrayList<>();
res.add(-1);
return res;
}
}
private boolean helper(TreeNode root, int[] arr) {
if (root == null) return true;
else if (root.val != arr[curr]) return false;
curr++;
if (root.left != null && root.left.val != arr[curr]) {
res.add(root.val);
return helper(root.right, arr) && helper(root.left, arr);
} else {
return helper(root.left, arr) && helper(root.right, arr);
}
}
}