四种根据给定遍历序列构造二叉树总结（JAVA递归和非递归版）

Mangena ·

更新时间:2024-11-13

· 907 次阅读

构造二叉树根据前序与中序遍历序列构造二叉树根据先序遍历构造二叉搜索树根据中序与后序遍历序列构造二叉树根据前序与后序遍历序列构造二叉树
二叉树的遍历顺序及方法可参考之前写过的二叉树的遍历（JAVA递归和非递归版）这里解决的是如何根据给定的遍历序列构造二叉树的问题。 根据前序与中序遍历序列构造二叉树

该问题中，会给出二叉树的前序与中序的遍历序列（没有重复元素）preorder和inorder，还原二叉树。

递归版（哈希表）：

前序序列第一个值一定是根节点的值；根据得到的根节点，在中序序列中可以得到二叉树根的索引 index，index的左边的值的个数即二叉树左子树节点的个数，左闭右开区间为（0,index），index的右边的值的个数即二叉树右子树节点的个数，左闭右开区间为（index+1,inorder.length）中序序列中的左子树区域（0,index）即前序序列中的（1，index+1）,同理可得二叉树前序序列中的右子树区域

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int preIndex=0;
    int[] preorder;
    int[] inorder;
    HashMap indexMap=new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder=preorder;
        this.inorder=inorder;
        int idx=0;
        for(Integer val:inorder) indexMap.put(val,idx++);
            return help(0,inorder.length);
    }
    public TreeNode help(int inLeft,int inRight){
    	//若左边界等于右边界，说明区域为空，也就是没有值需要被构造成节点了
        if(inLeft==inRight)return null;
        //根据前序序列的第一个节点构造二叉树的根节点
        int rootVal=preorder[preIndex++];
        TreeNode root=new TreeNode(rootVal);
        //找出根节点在中序序列中的位置
        int index=indexMap.get(rootVal);
        //对左子树和右子树进行递归
        root.left=help(inLeft,index);
        root.right=help(index+1,inRight);
        return root;
    }
}

递归版（不使用额外空间，也无需每次查找根节点在中序序列中的位置）：

class Solution {
    int pre=0;
    int in=0;
    int[] preorder;
    int[] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder=preorder;
        this.inorder=inorder;
        //stop是右边界，初始化stop的值为Integer.MAX_VALUE+1，也就是说stop的初始值不会是序列中任意一个数
        return help((long)Integer.MAX_VALUE+1);
    }
     private TreeNode help(long stop){
        if(pre==preorder.length)return null;
        //递归左边界一直是in，当in=stop时递归停止
        if(inorder[in]==stop){
            in++;
            return null;
        }
        int rootVal=preorder[pre++];
        TreeNode root=new TreeNode(rootVal);
        //左子树递归将每次根节点的值赋予stop，stop的右边是左子树
        root.left=help(rootVal);
        //右子树的右边界就是整棵树的stop,也就是序列中不存在的初始值
        root.right=help(stop);
        return root;
   }
}

非递归版（迭代，栈）

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0)return null;
        Stack roots=new Stack();
        int pre=0;
        int in=0;
        TreeNode currRoot=new TreeNode(preorder[pre++]);
        TreeNode root=currRoot;
        roots.push(currRoot);
        while(pre<preorder.length){
            if(currRoot.val==inorder[in]){
                while(!roots.isEmpty()&&roots.peek().val==inorder[in]){
                    currRoot=roots.pop();                    
                    in++;
                }
                currRoot.right=new TreeNode(preorder[pre++]);
                currRoot=currRoot.right;
                roots.push(currRoot);
            }
             else{
                currRoot.left=new TreeNode(preorder[pre++]);
                currRoot=currRoot.left;
                roots.push(currRoot);
            }
        }
        return root;
    }
}

根据先序遍历构造二叉搜索树

该问题中，会给出二叉树的前序序列（没有重复元素）preorder，要求返回二叉搜索树。
思考时一定要考虑到二叉搜索树的特性：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。若是有所遗忘可参考二叉搜索树百度百科
二叉搜索树的中序遍历序列是从小到大的已排序序列。根据给定的前序遍历序列，排序后可得到所求二叉搜索树的中序遍历序列，那么这个问题就是根据前序与中序遍历序列构造二叉树

递归版：

class Solution {
    int pre=0;
    int in=0;
    int[] preorder;
    int[] inorder;
    public TreeNode bstFromPreorder(int[] preorder) {
        this.preorder=preorder;
        inorder=Arrays.copyOf(preorder, preorder.length);
        Arrays.sort(inorder);
        return buildTreeHelp((long)Integer.MAX_VALUE+1);
    }
    private TreeNode buildTreeHelp(long stop){
        if(pre==preorder.length)return null;
        if(inorder[in]==stop){
            in++;
            return null;
        }
        int rootVal=preorder[pre++];
        TreeNode root=new TreeNode(rootVal);
        root.left=buildTreeHelp(rootVal);
        root.right=buildTreeHelp(stop);
        return root;
    }
}

非递归版：

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        int[] inorder=Arrays.copyOf(preorder, preorder.length);
        Arrays.sort(inorder);
        if(preorder.length==0)return null;
        Stack roots=new Stack();
        int pre=0;
        int in=0;
        TreeNode currRoot=new TreeNode(preorder[pre++]);
        TreeNode root=currRoot;
        roots.push(currRoot);
        while(pre<preorder.length){
            if(currRoot.val==inorder[in]){
                while(!roots.isEmpty()&&roots.peek().val==inorder[in]){
                    currRoot=roots.pop();                    
                    in++;
                }
                currRoot.right=new TreeNode(preorder[pre++]);
                currRoot=currRoot.right;
                roots.push(currRoot);
            }
            else{
                currRoot.left=new TreeNode(preorder[pre++]);
                currRoot=currRoot.left;
                roots.push(currRoot);
            }
        }
        return root;
    }
}

根据中序与后序遍历序列构造二叉树

该问题中，会给出二叉树的中序与后序的遍历序列（没有重复元素）inorder和postorder，还原二叉树。
这个问题也与根据前序与中序遍历序列构造二叉树相似，根据中序遍历序列确定左右子树区间，根据后序遍历序列确定根节点。
递归版：

class Solution {
    int postIndex;
    int[] postorder;
    int[] inorder;
    HashMap indexMap=new HashMap();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        this.inorder = inorder;
        postIndex=postorder.length-1;
        int idx=0;
        for(Integer val:inorder)indexMap.put(val,idx++);
        return help(0,inorder.length-1);   
    }
    public TreeNode help(int inLeft,int inRight){
        if(inLeft>inRight)return null;
        int rootVal=postorder[postIndex--];
        TreeNode root = new TreeNode(rootVal);
        int index=indexMap.get(rootVal);
        //因为是后序和中序，所以在这里先递归右子树
        root.right=help(index+1,inRight);
        root.left=help(inLeft,index-1);
        return root;
    }
}

非递归版（栈）：

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (postorder.length == 0) {
        return null;
    }
    Stack roots = new Stack();
    int post = postorder.length - 1;
    int in = inorder.length - 1;
    TreeNode currRoot = new TreeNode(postorder[post--]);
    TreeNode root = currRoot;
    roots.push(currRoot);
    while (post >=  0) {
        if (currRoot.val == inorder[in]) {
            while (!roots.isEmpty() && roots.peek().val == inorder[in]) {
                currRoot = roots.peek();
                roots.pop();
                in--;
            }
            currRoot.left = new TreeNode(postorder[post--]);
            currRoot = currRoot.left;
            roots.push(currRoot);
        } else {
            currRoot.right = new TreeNode(postorder[post--]);
            currRoot = currRoot.right;
            roots.push(currRoot);
        }
    }
    return root;
    }
}

根据前序与后序遍历序列构造二叉树

该问题中，会给出二叉树的前序与后序的遍历序列（没有重复元素）preorder和postorder，还原二叉树。

递归版：
因为前序是根左右的结构，后序是左右根的结构，所以可以考虑先建完左子树再考虑建右子树的问题

class Solution {
    int preIndex=0;
    int postIndex=0;
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        TreeNode root = new TreeNode(pre[preIndex++]);
        //建左子树
        if(root.val!=post[postIndex])root.left=constructFromPrePost(pre,post);
        //建右子树
        if(root.val!=post[postIndex])root.right=constructFromPrePost(pre, post);
        postIndex++;
        return root;
    }
}

作者：Ming宸

JAVA 二叉树 java递归遍历

1024 个赞