关于java:根据前序遍历和中序遍历来构造二叉树

leetCode105.#### 从前序与中序遍历序列结构二叉树
明天刷到了这个题,看到了大佬的奇妙思路,记录一下学习过程。

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

递归真香

1.应用指针p_start和p_end来别离记录前序遍历数组的起始和末位。
2.应用指针i_start和i_end 来别离记录中序遍历数组的起始和末位。

1.终止条件

p_start=p_end,阐明曾经遍历完子树所有元素

2.递推

根节点索引index
root.left=(pre,start+1,start+子数组的length,in,start,index);
roo.right=(pre,start+子数组的长度length,p_end,in,index+1,i_end);

3.返回值

return root;
public TreeNode buildTree(int[] preoder,int[] inorder){
        return buildTree(preoder,0,preoder.length,inorder,0,inorder.length);
    }

private TreeNode buildTree(int[] preoder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
        if(p_start==p_end){
            return null;
        }

        int root_val=preoder[p_start];
        TreeNode root=new TreeNode(root_val);

        int i_root_index=-1;
        for (int i = i_start; i <i_end; i++) {
            if(root_val==inorder[i]){
                i_root_index=i;
                break;
            }
        }

        //左子树数组长度-1
        int leftNum=i_root_index-i_start;

        //递归左子树
        root.left=buildTree(preoder,p_start+1,p_start+leftNum+1,inorder,i_start,i_root_index);
        //递归右子树
        root.right=buildTree(preoder,p_start+leftNum+1,p_end,inorder,i_root_index+1,i_end);
        return root;
    }

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理