力扣-数据结构-10【算法学习day.81】

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.反转二叉树以匹配先序遍历

题目链接:971. 翻转二叉树以匹配先序遍历 - 力扣（LeetCode）

题面:

附上大佬代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    List<Integer> ans = new ArrayList<>();
    int idx = -1;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        return dfs(root, voyage) ? ans : Arrays.asList(-1);
    }

    boolean dfs(TreeNode node, int[] voyage) {
        // 空节点肯定满足, 直接返回 true
        if (node == null) { return true; }

        idx++;
        // 检查当前节点的值和 voyage 数组对应位置的值是否一致
        if (node.val != voyage[idx]) { return false; }
        // 需要进行翻转的情况
        if (node.left != null && node.right != null &&
            node.left.val != voyage[idx+1]) {
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            ans.add(node.val);
        }
        // 递归处理左子树和右子树
        return dfs(node.left, voyage) && dfs(node.right, voyage);
    }
}

后言

上面是数据结构相关的习题，下一篇文章会将其他相关的习题。