leetcode刷题（97）——105. 从前序与中序遍历序列构造二叉树

老马的编程之旅

发布于 2022-06-22 14:04:15

1670

发布于 2022-06-22 14:04:15

文章被收录于专栏：深入理解Android

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1.先回顾前序遍历和中序遍历的框架：

void traverse(TreeNode root) {
    // 前序遍历
    preorder.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

void traverse(TreeNode root) {
    traverse(root.left);
    // 中序遍历
    inorder.add(root.val);
    traverse(root.right);
}

通过上面的图观察规律，前序遍历第一个值肯定是根结点，中序遍历，根结点左边都是左子树，右边都是右子树

对于preorder数组呢？如何确定左右数组对应的起始索引和终止索引？

这个可以通过左子树的节点数推导出来，假设左子树的节点数为leftSize，那么preorder数组上的索引情况是这样的：

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helpBuild(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    private TreeNode helpBuild(int[] preorder,int preStart,int preEnd,
    int[] inorder,int inorderStart,int inordorEnd){
        if(preStart>preEnd){
            return null;
        }
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int index = 0;
        for(int i=0;i<=inordorEnd;i++){
            if(rootVal == inorder[i]){
                index = i;
                break;
            }
        }
        int leftSize = index - inorderStart;
        root.left = helpBuild(preorder,preStart+1,preStart+leftSize,inorder,
        inorderStart,index-1);
        root.right = helpBuild(preorder,preStart+leftSize+1,preEnd,inorder,
        index+1,inordorEnd);
        return root;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-01-04，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法