LeetCode 105. 从前序与中序遍历序列构造二叉树

解法一 递归

思路

前序遍历顺序为 中 - 左 - 右,中序遍历的顺序为 左 - 中 - 右。这意味着前序遍历的第一个元素必为根节点,我们需要在中序遍历中找到这个节点的索引,随后中序遍历数组中这个索引左边的数组是左子树,右边的所有元素是右子树。

代码
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
            return null;
        }

        return helper(preorder, inorder, 0, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] preorder, int[] inorder, int preSt, int inSt, int inEnd) {
        if (inSt > inEnd || preSt > preorder.length) {
            return null;
        }

        // Set the first value in preorder as root node
        TreeNode head = new TreeNode(preorder[preSt]);

        // Look for the root node index in inorder traversal
        int i = inSt;
        while (i <= inEnd) {
            if (inorder[i] == preorder[preSt]) {
                break;
            }
            i++;
        }

        // 设置左子树和右子树。
        // 左子树在 preorder 中从根节点后一个数开始(我们只需要这个索引,因为我们只需在 preorder 数组中找到根节点的值)。在 inorder 中左子树从 inSt 到 i - 1 结束。
        // 右子树在 preorder 中从左子树结束后的位置开始,为了找到这个索引,我们要根据 inorder 数组计算左子树长度,为 (i - inSt)。在 inorder 中右子树从 i + 1 到 inEnd 结束。
        head.left = helper(preorder, inorder, preSt + 1, inSt, i - 1);
        head.right = helper(preorder, inorder, preSt + (i - inSt) + 1, i + 1, inEnd);

        return head;
    }
}
复杂度分析
  • 时间复杂度
    • O(n)
  • 空间复杂度
    • O(n)
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!