Leetcode 971 Flip Binary Tree to Match Preorder Traversal

发表于 |

给定一个有 N 个节点的二叉树，每个节点都有一个不同于其他节点且处于 {1, …, N} 中的值。
通过交换节点的左子节点和右子节点，可以翻转该二叉树中的节点。
考虑从根节点开始的先序遍历报告的 N 值序列。将这一 N 值序列称为树的行程。

我们的目标是翻转最少的树中节点，以便树的行程与给定的行程 voyage 相匹配。
如果可以，则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。
如果不能，则返回列表 [-1]。


Note:

  1. 1 <= N <= 100

思路分析：
假设当前结点为root，那么只要判断给定的数组是否满足以下两种形式即可

  1. [root.val, root.left.val,….., root.right.val,…..]
  2. [root.val, root.right.val,….., roo.left.val,……]
    当然需要考虑到可能没有左孩子或右孩子的情况

虽然思路很简单，但单纯的用if else逻辑来写会让这道题的代码显得很杂乱，我们注意到树里面给定的所有值和voyage里面的所有值都是各不相同并且是属于1，N的。这一点能让我们使用一点技巧将代码变短。

在讲具体方法的时候，这里先思考一个问题，我们平常是如何判断一个数组是一棵树的先序遍历情况呢？
显然，如果我们新开一个数组来保存先序遍历的值，然后和给定数组进行比较是完全ok的，但这新建了O(n)的空间，我们是可以不用开新空间的（书本知识）

1
2
3
4
5
6
7
8
# 当然有迭代写法，这里写一个递归的方法
index = 0
def check(root, nums):
    if not root: return True
    if root.val != nums[index]:
        return False
    index += 1
    return check(root.left, nums) and check(root.right, nums)

这里我们也可以采用同样的思路，依次遍历结点，只有出现有左子树且左孩子的节点值不等于当前index指向的值，才交换左右孩子，其余情况正常遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def flipMatchVoyage(self, root, voyage):
        self.index = 0
        res = []
        def dfs(root):
            if not root: return True
            if root.val != voyage[self.index]: return False
            self.index += 1
            # 有左子树，且左子树的节点值不等于当前index指向的值
            if root.left and root.left.val != voyage[self.index]:
                if not root.right: return False
                res.append(root.val)
                # 此时先右再左
                return dfs(root.right) and dfs(root.left)
            return dfs(root.left) and dfs(root.right)

        if dfs(root):
            return res
        return [-1]

96 / 96 test cases passed.
diffculty: medium
Runtime: 36 ms