问题描述
You are given the root of a binary tree with n nodes, where each node is uniquely assigned a value from 1 to n. You are also given a sequence of n values voyage, which is the desired pre-order traversal of the binary tree.
Any node in the binary tree can be flipped by swapping its left and right subtrees. For example, flipping node 1 will have the following effect:
Flip the smallest number of nodes so that the pre-order traversal of the tree matches voyage.
Return a list of the values of all flipped nodes. You may return the answer in any order. If it is impossible to flip the nodes in the tree to make the pre-order traversal match voyage, return the list [-1].
Example 1:
Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.
Example 2:
Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]
Explanation: Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.
Example 3:
Input: root = [1,2,3], voyage = [1,2,3]
Output: []
Explanation: The tree’s pre-order traversal already matches voyage, so no nodes need to be flipped.
Constraints:
- The number of nodes in the tree is n.
- n == voyage.length
- 1 <= n <= 100
- 1 <= Node.val, voyage[i] <= n
- All the values in the tree are unique.
- All the values in voyage are unique.
问题分析
首先，我们回顾下二叉树的前序遍历：先root，再左子树，最后右子树；对于子树，也是递归以上过程。
如果有同学经常对二叉树的前序、中序、后序遍历混淆的，记住一点：所谓前、中、后都是指遍历过程中root节点的相对顺序；以前序为例：即优先遍历root；对于中序：则优先遍历左子树，然后root，然后右子树。后序则是先左子树，后右子树，最后root节点。
对于这道题，按照前序遍历规则：root之后紧跟着应该访问的是左子树的root，也即root.Left节点。体现在前序遍历的voyage里，即voyage[i]与voyage[i+1]。所以从root开始，如果root.Left存在且root.Left.Value与voyage中对应的值不相等，则将当前root.Value保存入ans，同时将root.Left, root.Right进行交换。然后递归以上过程。
在处理过程中，需要注意i+1是否越界。
在处理完后，需要对交换后的树进行一次前序遍历，看最终结果和voyage是否一致；如果仍然不一致，则返回-1。这里仍然需要再次进行前序遍历的原因是：对于某些左子树为null，同时voyage为不可能顺序的情况，程序返回为空；需要进行一次前序遍历，来确定树原本就已经符合voyage的遍历顺序，还是不可能调整为voyage导致返回结果为空。
示例代码如下
示例代码
初始解法
func flipMatchVoyage(root *TreeNode, voyage []int) []int {
ans := []int{}
m := make(map[int]int)
for k, v := range voyage {
m[v] = k
}
flip(root, voyage, m, &ans)
// check
po := []int{}
preorder(root, &po)
for i := 0; i < len(po); i++ {
if po[i] != voyage[i] {
return []int{-1}
}
}
return ans
}
func flip(root *TreeNode, voyage []int, m map[int]int, ans *[]int) {
if root == nil {
return
}
rootidx := m[root.Val]
if root.Left != nil {
if rootidx+1 >= len(voyage) {
*ans = append(*ans, -1)
return
}
if voyage[rootidx+1] != root.Left.Val {
// need flip
root.Left, root.Right = root.Right, root.Left
*ans = append(*ans, root.Val)
}
}
if root.Left != nil {
flip(root.Left, voyage, m, ans)
}
if root.Right != nil {
flip(root.Right, voyage, m, ans)
}
}
func preorder(root *TreeNode, ans *[]int) {
if root == nil {
return
}
*ans = append(*ans, root.Val)
if root.Left != nil {
preorder(root.Left, ans)
}
if root.Right != nil {
preorder(root.Right, ans)
}
}
优化解法
上述解法已经可以Accepted，提交后，在讨论区查看其他用户解答时，发现初始解法还是稍显繁琐，不够精简。故仔细阅读他人的一种优化解法后，重新写了一遍。
该解法的核心逻辑和初始解法类似，都是递归判断root.Left.Value是否与voyage中对应的值相等，如果不等，则将root.Value加入到ans中。
但是，该解法巧妙的点在于：
- 使用了全局变量idx来控制遍历过程中需要访问的voyage下标
- 方法返回了一个bool类型结果，用来表示当前树是否满足遍历条件
- 在确定
root.Left需要flip之后，不是直接交换左右2个节点，而是优先遍历root.Right,再遍历root.Left， 达到和交换一样的遍历目的
该方法以dfs递归方法的返回值来判断某棵树是否能按照条件遍历，省去了初始解法里最后仍需再前序遍历一次进行判断的过程；更换遍历顺序，而不是直接交换的处理也进一步使得代码更为精炼。
// concise ver
var idx int
func flipMatchVoyageV2(root *TreeNode, voyage []int) []int {
// init before multi run
idx = 0
ans := []int{}
res := dfs(root, voyage, &ans)
if !res {
return []int{-1}
}
return ans
}
func dfs(root *TreeNode, voyage []int, ans *[]int) bool {
if root == nil {
return true
}
if voyage[idx] != root.Val {
return false
}
idx++
if root.Left != nil && root.Left.Val != voyage[idx] {
*ans = append(*ans, root.Val)
// flip traversal
return dfs(root.Right, voyage, ans) && dfs(root.Left, voyage, ans)
}
return dfs(root.Left, voyage, ans) && dfs(root.Right, voyage, ans)
}