leetcode- 从前序与中序遍历序列构造二叉树

题目地址:从前序与中序遍历序列构造二叉树

解题思路

解题思路来自左程云老师的算法课新手班第六节

先序,中序都可以展示出树的结构,先序是头左右,中序是左头右。

由先序可以得出树的头节点,因为题目上数据条件上说,均无重复元素。

说明,只需要在中序中遍历到和先序数组第一个元素值相同的元素,它的前面就是左树,后面就是右树,在先序中,也可以根据这个左树的个数去得到左树和右树的下标范围。

所以:定义find,遍历数组,在in(中序数组)中找到头

int find=L2;
while (in[find]==pre[L1]){
    find++;
}

根据这个find就可以知道这个头节点下方左树和右树的规模,左树规模为 [L1,find-1],右树规模为[ find+1,R2 ].

而我们的目标是建立一颗完整的树,也就是每个节点都必须建立,

先建立出头节点

TreeNode head = new TreeNode(pre[L1]);

接着去考虑头节点的左右树,这时就需要考虑递归

我们需要去新创建一个方法,将先序数组,中序数组,都传进去。

建立好头节点之后,该节点的左右树,左树将左树在先序和中序的范围传入,右树将右树在先序和中序的范围传入如此接着建立。

head.left = build(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
head.right = build(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);

边界条件判断

如果传入的数组为空,或者两个数组长度不一致,那么直接返回空

if (preorder == null || inorder == null || preorder.length != inorder.length) {
   return null;
}

如果L1=R1,说明该节点下方为空,直接返回该节点即可

if (L1 == R1) {
    return head;
}

假如L1>R1,说明该节点下方并非左右都有

比如先序为[1,2,3],中序也是[1,2,3]。那么树的结构应该为1右树为2,2右树为3,但是这样在调用方法时,

build(pre, L1 + 1, L1 + find – L2, in, L2, find – 1),find为0,L1+1(也就是下一次的L1)为1,L1+find-L2(也就是下一次的R1)为-1,1>-1,所以返回null

if(L1>R1){
   return null;
}

完整代码

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    public TreeNode build(int[] pre, int L1, int R1, int[] in, int L2, int R2) {
        if(L1>R1){
            return null;
        }
        int find = L2;
        while (in[find] != pre[L1]) {
            find++;
        }
        TreeNode head = new TreeNode(pre[L1]);
        if (L1 == R1) {
            return head;
        }
        head.left = build(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
        head.right = build(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
        return head;
    }
版权声明:除特殊说明,博客文章均为栋dong原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
如有需要,请在留言板留言,或者添加我的QQ或者微信
我只是一个学生,如有错误或者侵权,请联系我,谢!

评论

  1. 博主
    Windows Edge
    3 月前
    2024-1-16 19:54:30

    Copyright © 2022 – 2023 版权所有 栋dong ( ๑´•ω•) “(ㆆᴗㆆ)

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇