LeetCode题解|971. Flip Binary Tree To Match Preorder Traversal

题目链接：971. Flip Binary Tree To Match Preorder Traversal

概述

这个题目给定了一棵有N个节点的二叉树以及一个序列v，问如何翻转最少的节点（交换左右子树），使得前序遍历结果和给定的序列一致。

思路

使用DFS前序遍历这棵树，并且使用一个指针i，记录当前节点node应该和v中的哪个值相等，DFS时，可分为以下三种情况：

1. node === null，说明我们已经遍历完了，返回true
2. node.val !== v[i]，说明该节点值不是预期的，返回false
3. node.left.!== null && node.left.val !== v[i]，说明左儿子存在但是其值并不是预期的，此时，我们应该翻转node节点，但是我们并不需要真的去修改指针，只要先去遍历右子树，再去遍历左子树，即可达到翻转并且前序遍历的目的。

实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number[]} voyage
 * @return {number[]}
 */
var flipMatchVoyage = function(root, voyage) {
    var result = [];
    var i = 0;
    var dfs = function(node){
        if(node == null){
            return true;
        }
        if(node.val != voyage[i++]){
            return false;
        }
        if(node.left != null && node.left.val != voyage[i]){
            result.push(node.val);
            return dfs(node.right) && dfs(node.left);
        }
        return dfs(node.left) && dfs(node.right);
    }
    
    return dfs(root) ? result : [-1];
};

题解合集