前端就该用 JS 刷算法2

题目

翻转二叉树以匹配前序遍历

过程

• 在最开始做题的时候，是想根据完全二叉树的方式来判断左右节点的值是否需要翻转，但是 voyage 并不会将所有 null 节点引入，所以找的 pos 和 voyage 数组的 index 是不匹配的，所以方案挂掉了
• 然后考虑的问题都是根节点的值不变，考察左右节点的值，导致对题目理解出现了偏差
• 题目说的翻转是整个子树都翻转，也就是如果某个节点 root 需要翻转，那么它的前序遍历就是先右后左，否则就是正常的先左后右
• 所以我们只需要按需先序遍历即可
• 能左走就左走，不能就右走，每次走完右子树要判断一下下一个 pos 是否和左树节点的值一致，如果一致，那证明可以先右走再左走
• 最后只需要判断一下 pos 和 voyage 的长度是否一致，就可以知道有没有遍历全树

// https://leetcode-cn.com/problems/flip-binary-tree-to-match-preorder-traversal/
/**
 * 
 * @分析
 * 1. 翻转的概念：交换节点 root 的左右节点
 * 2. 反转最少的树中节点
 * 
 */
var flipMatchVoyage = function (root, voyage) {
    let res = []
    let pos = 0
    const dfs = (root) => {
        // 只有当根节点相等的时候才会继续走,只是为了判断根节点
        if (root.val !== voyage[pos]) return
        pos++
        // 前序遍历
        if (root.left && root.left.val === voyage[pos]) {
            dfs(root.left)
        }
        if (root.right && root.right.val === voyage[pos]) {
            // 走右侧的树了
            dfs(root.right)
            // 走完之后再测一下是否是需要交换，如果是正常走，这个条件是不能触发的
            if (root.left && root.left.val === voyage[pos]) {
                res.push(root.val)
                // 继续走左树
                dfs(root.left)
            }
        }
    }
    dfs(root)
    if(pos !== voyage.length){
        // 没有走完，所以不符合可翻转得到前序遍历这种情况
        return [-1]
    }
    return res
};

小结

第二天刷中等的没遇到过的树题，还是没有在 1h 做出来，最后是看题解完成的，所以对于树题还是不够熟悉，明天需要先将树的文章再过一遍再做题目