重建二叉树

在安全路上的白白 lv.1

发布时间：2023-08-27 18:13:34 295

相关标签：

二叉树的存储结构：

主要采用链式存储结构，顺序存储结构仅适用于完全二叉树（满二叉树）。
将完全二叉树的结点按次序进行编号，实际上是对完全二叉树的一次层次遍历。
完全二叉树能够采用顺序存储结构存储，依靠数组元素的相邻位置反映完全二叉树的逻辑结构。所以，完全二叉树能够采用顺序储存结构存储，依靠元素的相邻位置反映完全二叉树的逻辑结构。
由于顺序存储结构没有特别的存储元素间的关系，不存在一棵二叉树与一种线性序列是一对一的映射，所以，非完全二叉树不能采用顺序存储结构存储。
二叉树的链式存储结构主要有二叉链表和三叉链表。（区别是：三叉链表增加了一个地址域parent指向其父母结点。）

构造一棵二叉树必须明确以下两种关系：

1.结点与其父母结点及孩子结点之间的层次关系；
2.兄弟结点之间左或右的次序关系。

三种能够唯一确定一棵二叉树的表示法：

由于先根次序或后根次序反映父母与孩子结点的层次关系，中根次序反映兄弟结点间的左右次序。
1.已知先根和中根两种遍历序列；
2.已知中根和后根两种遍历序列；
3.标明空子树的先根序列表示。

问题分析

已知先序遍历序列和中序遍历序列，根据两个遍历序列重建二叉树。
结题思路：
一、先遍历先序序列，第一个值即为树的根结点；遍历中序序列（假设没有重复的元素）与先序序列中的第一个值相同的值即为根结点，剩下的元素即为左子树和右子树的元素；
（第一步找到了根结点与左右子树。）
二、遍历先序序列中除了根结点（紧跟根结点）的元素，第一个元素即为左子树的根结点，元素数量与之前遍历中序序列的找出的左子树数量一样。。。。
三、这是个递归过程。详细内容还得慢慢领悟》看代码。

//重建二叉树
public class Solution8 {
    //Definition for binary tree
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return build(pre,in,0,pre.length-1,0,in.length-1);
    }

    public static TreeNode build(int[] pre, int[] in, int pstart, int pend, int istart, int iend){ //递归过程
        //传入参数：先序遍历序列数组、中序遍历序列数组、先序遍历开始位置、先序遍历结束位置、中开始、中结束
        if(pstart>pend) return null; //判断有效
        int cur = pre[pstart];//根节点，先序遍历数组开始位置即为根结点
        int find = istart;
        while(find<=iend){//在中序遍历中查找根节点
            if(cur==in[find]) break;
            else find++;
        }
        int len = find-istart;
        TreeNode res = new TreeNode(cur);//创建根节点
        //System.out.println(res+" ");
        res.left = build(pre,in,pstart+1,pstart+len,istart,find-1);//创建左子树
        res.right = build(pre,in,pstart+len+1,pend,find+1,iend);//创建右子树
        return res;
    }
    public static void main(String args[]){
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        //reConstructBinaryTree(pre,in);
    }
}

文章来源： https://blog.51cto.com/u_13618048/5891453

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。