# 翻转二叉树以匹配先序遍历 - Flip Binary Tree To Match Preorder Traversal

【先序遍历】

（回想一下，节点的先序遍历意味着我们报告当前节点的值，然后先序遍历左子节点，再先序遍历右子节点。）

### Example:

``````输入：root = [1,2], voyage = [2,1]

``````

``````输入：root = [1,2,3], voyage = [1,3,2]

``````

``````输入：root = [1,2,3], voyage = [1,2,3]

``````

## Solutions

 ``````1 2 3 4 5 6 7 8 `````` ``````Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } ``````

### Solution 【先序遍历】 ( 8ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 `````` ``````class Solution { List result = new LinkedList<>(); int i = 0; public List flipMatchVoyage(TreeNode root, int[] voyage) { boolean res = preOrderTraverse(root, voyage); if(!res){ result.clear(); result.add(-1); } return result; } public boolean preOrderTraverse(TreeNode node, int[] voyage) { if (node == null) return true; if(node.val != voyage[i]) return false; int left = 0; int right = 0; if(node.left != null) left = node.left.val; if(node.right != null) right = node.right.val; if(left != 0 && right != 0) { if(left != voyage[i+1]) { //尝试翻转 result.add(node.val); TreeNode tmp = node.right; node.right = node.left; node.left = tmp; } } i++; boolean res_left = preOrderTraverse(node.left, voyage); boolean res_right = preOrderTraverse(node.right, voyage); return res_left && res_right; } } ``````

### Solution 【考点标签】 ( 5ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 `````` ``````class Solution { int[] v; List ret; public List flipMatchVoyage(TreeNode root, int[] voyage) { ret=new ArrayList(); if(root==null)return ret; v=voyage; boolean re=real(root,0,voyage.length-1); if(!re) { ret.clear(); ret.add(-1); return ret; } return ret; } boolean real(TreeNode root,int left,int right) { if(left>right||root.val!=v[left])return false; if(root.left==null&&root.right==null&&left!=right)return false; if(root.left==null&&root.right==null)return true; if(root.left==null&&root.right!=null)return real(root.right,left+1,right); if(root.left!=null&&root.right==null)return real(root.left,left+1,right); int tleft=0,tright=0; for(int i=left+1;i<=right;i++) { if(root.left.val==v[i])tleft=i; if(root.right.val==v[i])tright=i; } if(tleft>tright) { ret.add(root.val); return real(root.right,tright,tleft-1)&&real(root.left,tleft,right); } return real(root.left,tleft,tright-1)&&real(root.right,tright,right); } } ``````