給定一個有 N 個節點的二叉樹,每個節點都有一個不同于其他節點且處于 {1, …, N} 中的值。
通過交換節點的左子節點和右子節點,可以翻轉該二叉樹中的節點。
考慮從根節點開始的先序遍歷報告的 N 值序列。將這一 N 值序列稱為樹的行程。
(回想一下,節點的先序遍歷意味著我們報告當前節點的值,然后先序遍歷左子節點,再先序遍歷右子節點。)
我們的目標是翻轉最少的樹中節點,以便樹的行程與給定的行程 voyage 相匹配。
如果可以,則返回翻轉的所有節點的值的列表。你可以按任何順序返回答案。
如果不能,則返回列表 [-1]。
代碼
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {int pos=0;List<Integer> r=new ArrayList<>();public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {flip(root,voyage);return r;}public void flip(TreeNode root,int[] voyage) {if(root==null||r.size()>0&&r.get(0)==-1) return;//如果出現了不滿足的情況或者節點為空直接返回if(root.val!=voyage[pos])//交換完還是不符合則返回-1{r.clear();r.add(-1);return ;}if(root.left!=null&&root.left.val!=voyage[pos+1])//如果不符合則交換左右子樹{TreeNode temp=root.left;root.left=root.right;root.right=temp;r.add(root.val);//將需要交換子樹的節點入隊}pos++;flip(root.left,voyage);flip(root.right,voyage);}
}