标签： 二叉树

目标

给出一个满足下述规则的二叉树：

1. root.val == 0
2. 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
3. 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

• FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
• bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

说明：

• TreeNode.val == -1
• 二叉树的高度不超过 20
• 节点的总数在 [1, 10^4] 之间
• 调用 find() 的总次数在 [1, 10^4] 之间
• 0 <= target <= 10^6

思路

dfs还原节点val，并将其加入到Hash表中，直接contains判断。

这个题被标为medium，估计是想让我们自己实现Hash表来查找元素吧。

代码

/**
 * @date 2024-03-12 2:41
 */
public class FindElements {
    Set<Integer> elements;

    public FindElements(TreeNode root) {
        elements = new HashSet<>();
        recover(root, 0);
    }

    public void recover(TreeNode root, int value) {
        if (root == null) {
            return;
        }
        root.val = value;
        elements.add(value);
        recover(root.left, 2 * value + 1);
        recover(root.right, 2 * value + 2);
    }

    public boolean find(int target) {
        return elements.contains(target);
    }
}

性能

目标

给你一棵二叉树的根节点 root 和一个正整数 k 。

树中的 层和 是指 同一层 上节点值的总和。

返回树中第 k 大的 层和（不一定不同）。如果树少于 k 层，则返回 -1 。

注意，如果两个节点与根节点的距离相同，则认为它们在同一层。

说明：

• 树中的节点数为 n
• 2 <= n <= 10^5
• 1 <= Node.val <= 10^6
• 1 <= k <= n

思路

这个问题的关键在于遍历的同时记录层数并进行累加。由于是升序排列所以取倒数第k个，即MAX-k。

代码

/**
 * @date 2024-02-23 16:06
 */
public class KthLargestLevelSum {
    public static 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;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public static void main(String[] args) {
        KthLargestLevelSum main = new KthLargestLevelSum();
        long res = main.kthLargestLevelSum(new TreeNode(1, new TreeNode(2), new TreeNode(3)), 2);
        System.out.println(res);
    }

    public final int MAX = 100000;
    public long[] lacc = new long[MAX];
    public int maxlevel = 0;

    public long kthLargestLevelSum(TreeNode root, int k) {
        traverseSubTree(root, 0);
        if (k > maxlevel + 1) {
            return -1;
        }
        Arrays.sort(lacc);
        return lacc[MAX-k];
    }
    public void traverseSubTree(TreeNode subTree, int level) {
        maxlevel = Math.max(maxlevel, level);
        lacc[level] += subTree.val;
        if (subTree.left != null) {
            traverseSubTree(subTree.left, level + 1);
        }
        if (subTree.right != null) {
            traverseSubTree(subTree.right, level + 1);
        }
    }
}

Arrays.sort使用的是双轴快排(DualPivotQuicksort)，时间复杂度是O(nlogn)。

性能

最优的算法是快速选择。因为我们并不需要所有的元素都有序，只要保证k位置的左侧都比k小，右侧均比k大即可，而两侧区间内部是不需要排序的。

目标

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

思路

本来看到这个题目觉得没什么新意，前面都已经做过 从前序与中序遍历序列构造二叉树 与 从中序与后序遍历序列构造二叉树这两个题目了，准备快速写一下。没想到，又花费了许多时间。虽然知道大体的方向，但真正写出来还是不那么容易的。对照着一个案例，按照大体思路写完解决方法之后，就急着去测试，结果有的例没有通过，有的数组越界。然后就开始调试，一会这加个判断，那处理一个特例，这个案例通过了，别的又不行了，一来二去就把自己绕晕了。之所以存在这样的情况还是对这个问题的理解不到位，没有一个清晰的思路。

有了前面的两道题的求解经验，我们知道这个题还是用递归求解更容易一些。求解的核心是遍历先序/后序序列，一个从前向后，一个从后向前。将遍历到的每一个节点去中序序列中找到相应位置然后划分左/右子树，然后递归处理子树。其实这里容易忽略一个问题，就是左/子树的节点一定会在先序/后序序列随后遍历中出现。可以根据这个来明确临界条件，否则容易漏掉或者弄错左右以及父节点。这也就是为什么先序序列先遍历左子树，后序先遍历右子树的原因。因为游标顺序移动，刚好可以覆盖相应的子树。刚开始我还想着分别在先序和后序维护两个游标，这是不可行的。

说回到这个题目，它不像前面两个那样可以明确左右子树。前面说前序序列的第二个节点是其左子树或右子树的根节点，并非是无法确定，而是需要结合实际情况看是否存在左子树，如果存在则一定是左子树根节点。这个可以在中序序列中找到相应位置就知道了。但是对于这个题而言左右是无法确定的，很简单的例子 [1,2] 与 [2,1]。

我们的思路是遍历先序序列，找到其在后序序列的位置，该位置减1则是可能的右根节点，反查其在先序序列中的位置。这样我们就得到了一个左子树区间或者单个节点（无法确定左右）。这样我们就可以递归构建左子树，对于单个节点的情况需要将搜索范围扩展到序列结尾，否则可能反查不到节点在先序序列中的位置。

代码

/**
 * @date 2024-02-23 10:05
 */
public class BuildBinaryTreeFromPrePost {
    public static 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;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public static int preCursor = 1;

    public static void main(String[] args) {
        BuildBinaryTreeFromPrePost main = new BuildBinaryTreeFromPrePost();
//        int[] preorder = new int[]{1,2,4,5,3,6,7};
//        int[] preorder = new int[]{3, 9, 20, 15, 7};
//        int[] preorder = new int[]{1,2};
//        int[] preorder = new int[]{2,1,3};
//        int[] preorder = new int[]{4,2,1,3};
        int[] preorder = new int[]{3,4,2,1};
//        int[] preorder = new int[]{1};
//        int[] postorder = new int[]{4,5,2,6,7,3,1};
//        int[] postorder = new int[]{1};
//        int[] postorder = new int[]{9, 15, 7, 20, 3};
//        int[] postorder = new int[]{2,1};
//        int[] postorder = new int[]{3,1,2};
//        int[] postorder = new int[]{3,1,2,4};
        int[] postorder = new int[]{2,1,4,3};
        System.out.println(main.constructFromPrePost(preorder, postorder));
    }

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        TreeNode root = new TreeNode(preorder[0]);
        if (preorder.length == 1) {
            return root;
        }
        int rightRootPreIndex = 0;
        for (int i = 0; i < preorder.length; i++) {
            if (postorder[postorder.length - 2] == preorder[i]){
                rightRootPreIndex = i;
                break;
            }
        }
        // 注意当start == end时，搜索长度应扩展到整个数组长度，否则会导致查询不到当前节点的右子树根节点。
        root.left = buildSubTree(preorder, postorder, preCursor, rightRootPreIndex == preCursor ? preorder.length:rightRootPreIndex);
        if (preCursor >= rightRootPreIndex && preCursor < preorder.length) {
            root.right = buildSubTree(preorder, postorder, rightRootPreIndex, preorder.length);
        }
        return root;
    }

    public TreeNode buildSubTree(int[] preorder, int[] postorder, int start, int end){
        TreeNode root = new TreeNode(preorder[preCursor]);
        int rightRootPostIndex = 0;
        int rightRootPreIndex = 0;
        for (int i = 0; i < postorder.length; i++) {
            if (root.val == postorder[i]){
                rightRootPostIndex = i;
                preCursor++;
                break;
            }
        }
        if (rightRootPostIndex > 0) {
            for (int i = start; i < end; i++) {
                if (postorder[rightRootPostIndex - 1] == preorder[i]) {
                    rightRootPreIndex = i;
                    break;
                }
            }
            if (preCursor < rightRootPreIndex) {
                root.left = buildSubTree(preorder, postorder, preCursor, rightRootPreIndex == 0 ? preorder.length : rightRootPreIndex);
            }
            if (preCursor >= rightRootPreIndex && preCursor < end && rightRootPreIndex !=0) {
                root.right = buildSubTree(preorder, postorder, rightRootPreIndex, end);
            }
        }
        return root;
    }
}

先序序列的初始条件是直接从第二个位置开始的，直接从后序序列的倒数第二个反查其在先序序列的位置。

性能

目标

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路

有了前面 从前序与中序遍历序列构造二叉树 的经验这个问题就很好处理了。二叉树的后序遍历指先访问左子树、再访问右子树，最后访问根节点。

只需从后序序列的最后一个元素向前遍历即可，最后一个是根节点，接着是右子树、左子树的根节点 （注意这里是先右后左）。

还是在中序遍历中找到该根节点，然后其左侧的为左子树，右侧为右子树。依次递归遍历右子树与左子树，在递归方法中根节点取后序序列的前一个节点即可。

代码

/**
 * @date 2024-02-21 14:12
 */
public class BuildBinaryTreeFromMidPost {
    public static 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;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

//    static int[] inorder = new int[]{9, 3, 15, 20, 7};
    static int[] inorder = new int[]{2,3,1};
//    static int[] inorder = new int[]{-1};

//    static int[] postorder = new int[]{9, 15, 7, 20, 3};
    static int[] postorder = new int[]{3,2,1};
//    static int[] postorder = new int[]{-1};

    static int postCursor = postorder.length - 1;

    public static void main(String[] args) {
        int rootIndex = 0;
        TreeNode root = new TreeNode(postorder[postCursor]);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == postorder[postCursor]) {
                rootIndex = i;
                // 一定能够找到
                postCursor--;
                break;
            }
        }
        int leftEndIndex = rootIndex - 1;
        int rightStartIndex = rootIndex + 1;
        // 注意这个postCursor应该是共享变量，原先是想以参数传递的，但是发现递归的时候还要将它传回来，改成了共享变量
        // 这里是先遍历右子树再左子树
        if (rightStartIndex < inorder.length) {
            root.right = traverseSubTree(inorder, rightStartIndex, inorder.length);
        }
        if (leftEndIndex >= 0) {
            root.left = traverseSubTree(inorder, 0, leftEndIndex);
        }
        System.out.println(root);
    }

    public static TreeNode traverseSubTree(int[] inorder, int start, int end) {
        TreeNode subRoot = new TreeNode(postorder[postCursor]);
        int rootIndex = start;
        for (int i = start; i <= end; i++) {
            if (inorder[i] == postorder[postCursor]) {
                rootIndex = i;
                postCursor--;
                break;
            }
        }
        int leftEndIndex = rootIndex - 1;
        int rightStartIndex = rootIndex + 1;
        // 临界条件判断，这里应该是<=，并且排除掉inorder.length
        // 这里是先遍历右子树再左子树
        if (rightStartIndex <= end && rightStartIndex != inorder.length) {
            // 这里的结束条件传end
            subRoot.right = traverseSubTree(inorder, rightStartIndex, end);
        }
        if (leftEndIndex >= start) {
            subRoot.left = traverseSubTree(inorder, start, leftEndIndex);
        }
        return subRoot;
    }
}

性能

目标

给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思路

首先要明白先序遍历与中序遍历的概念。所谓二叉树的 先序遍历 指的是 先访问根节点，然后遍历左子树，再遍历右子树。中序遍历 则是 先遍历左子树，再根节点，然后右子树。

很容易想到使用递归，关键点是数组左右边界的维护，临界条件的判断。

注意到 先序遍历数组的第一个节点一定是根节点，其后面的节点则是其左子树或右子树的根节点。

于是先根据根节点在中序遍历中找到该根节点，然后其左侧的为左子树，右侧为右子树。依次递归遍历左子树与右子树（注意判断边界条件），在递归方法中根节点取刚才根节点的后一个节点（需要一个共享变量来记录位置）。

代码

/**
 * @date 2024-02-20 11:43
 */
public class BuildBinaryTree {

    public static 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;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    static int[] preorder = new int[]{3, 9, 20, 15, 7};
//    static int[] preorder = new int[]{1,2,3};
//    static int[] preorder = new int[]{-1};

    static int[] inorder = new int[]{9, 3, 15, 20, 7};
//    static int[] inorder = new int[]{2,3,1};
//    static int[] inorder = new int[]{-1};

    static int preCursor = 0;

    public static void main(String[] args) {
        int rootIndex = 0;
        TreeNode root = new TreeNode(preorder[preCursor]);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[preCursor]) {
                rootIndex = i;
                // 一定能够找到
                preCursor++;
                break;
            }
        }
        int leftEndIndex = rootIndex - 1;
        int rightStartIndex = rootIndex + 1;
        if (leftEndIndex >= 0) {
            root.left = traverseSubTree(inorder, 0, leftEndIndex);
        }
        // 注意这个preCursor应该是共享变量
        if (rightStartIndex < inorder.length) {
            root.right = traverseSubTree(inorder, rightStartIndex, inorder.length);
        }
        System.out.println(root);
    }

    public static TreeNode traverseSubTree(int[] inorder, int start, int end) {
        TreeNode subRoot = new TreeNode(preorder[preCursor]);
        int rootIndex = start;
        for (int i = start; i <= end; i++) {
            if (inorder[i] == preorder[preCursor]) {
                rootIndex = i;
                preCursor++;
                break;
            }
        }
        int leftEndIndex = rootIndex - 1;
        int rightStartIndex = rootIndex + 1;
        if (leftEndIndex >= start) {
            subRoot.left = traverseSubTree(inorder, start, leftEndIndex);
        }
        // 临界条件判断，这里应该是<=，并且排除掉inorder.length
        if (rightStartIndex <= end && rightStartIndex != inorder.length) {
            // 这里的结束条件传end
            subRoot.right = traverseSubTree(inorder, rightStartIndex, end);
        }
        return subRoot;
    }
}

性能

我的目标是能解决问题就好，看了下性能分布还有优化的空间，官网还给出了迭代的解法，没时间看。递归应该是更容易理解的方法了。希望能够坚持下去吧。