105. Construct Binary Tree from Preorder and Inorder Travers

发布时间：2020-12-14 04:21:32 所属栏目：大数据来源：网络整理

导读：一、题目 1、审题 2、分析给出一个数值不重复的二叉树的先序、中序遍历的遍历顺序，求该二叉树的原始结构。 ? 二、解答 1、思路：分析二叉树的先序、中序遍历特点如下： ①、先序（preOrder）：?根 -- 左 -- 右； ②、中序（inOrder）：? 左--?根 --?右；

一、题目

　　1、审题

　　2、分析

　　　　给出一个数值不重复的二叉树的先序、中序遍历的遍历顺序，求该二叉树的原始结构。

二、解答

　　1、思路：

　　　　分析二叉树的先序、中序遍历特点如下：

　　　　①、先序（preOrder）：?根 --> 左 --> 右；

　　　　②、中序（inOrder）：? 左-->?根 -->?右；

　　　　③、先序的第一个节点为整颗二叉树的根节点（root），root?节点将中序序列分成两部分，root?左边的为?root?的左子树的所有子节点，root?右边的为?root?右子树的所有子节点；

　　　　④、先序的节点顺序在数组中正好是有序的；中序的节点顺序，若?index(node1) < index(node2)，则?node2?为?node1?的祖先节点，或者为祖先节点的右孩子节点，或者为?node1的右孩子或其子孙节点；

　　　　方法一、

　　　　　　采用递归方法。

　　　　　　①、以?preOrder?首节点作为?root，则?root?在?inOrder?中出现的下标为?index，

　　　　　　　　则?preOrder?的（1，index）的节点即为?root?的左子树的先序遍历顺序， inOrder?的 (0,index - 1)?即为?root?的左子树的中序遍历的顺序，

　　　　　　　　同理，preOrder?的（index +1,len - 1）?为?root?的右子树的先序遍历顺序，inOrder?的（index+1，len - 1）为?root?的右子树的中序遍历顺序。

　　　　　　②、递归的跳出条件为，root?在?preOrder?的下标 >?preOrder?的数组最大下标，或?inOrder?的?left > right。

public TreeNode buildTree(int[] preorder,int[] inorder) {
        
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for (int i = 0; i < inorder.length; i++) 
            map.put(inorder[i],i);
        return helper(0,inorder.length - 1,preorder,inorder,map);
    }
    
    private TreeNode helper(int preStart,int inStart,int inEnd,int[] preorder,int[] inorder,Map<Integer,Integer> map) {
        
        // 跳出递归条件
        if(preStart > preorder.length - 1 || inStart > inEnd)
            return null;
        
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = map.get(root.val);
        root.left = helper(preStart+1,inStart,inIndex - 1,map);
        root.right = helper(preStart + (inIndex - inStart + 1),inIndex + 1,inEnd,map);
        
        return root;
    }

　　方法二、

　　　　创建一个?Stack，?以先序遍历顺序依次入栈，入栈时，判断该节点在?中序遍历中与站顶元素的位置关系：

　　　　　　①、若?中序遍历中栈顶元素排在此节点前，?则此节点必为站顶节点的左孩子。

　　　　　　②、若中序遍历中站顶元素在此节点后边，则站顶依次出栈，直到栈为空，或者站顶元素在中序遍历的位置排在此节点值的后边；

　　　　　　　　此时，此节点必为前站顶元素的右孩子。

public TreeNode buildTree(int[] preorder,int[] inorder) {
       if(preorder.length == 0)
            return null;
        
        Map<Integer,i);
        
        Stack<TreeNode> stack = new Stack<>();
        int value = preorder[0];
        TreeNode root = new TreeNode(value);
        stack.push(root);
        
        for (int i = 1; i < preorder.length; i++) {
            value = preorder[i];
            TreeNode node = new TreeNode(value);
            
            if(map.get(value) < map.get(stack.peek().val)) {
                stack.peek().left = node;
            }
            else {
                TreeNode parent = null;
                while(!stack.isEmpty() && map.get(value) > map.get(stack.peek().val))
                    parent = stack.pop();    // stack 为空时跳出循环(即 node 为根节点右孩子)，
                                            // 或者 stack 栈顶元素在 inorder 中顺序大于 node 跳出循环(即 node 为前站顶的右孩子)
                parent.right = node;
            }
            stack.push(node);
        }
        return root;
    }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!