07_重建二叉树，根据先序和中序创建二叉树（中等难度）

男娘i 2023-03-06 03:39 17阅读 0赞

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = \[3,9,20,15,7\]  
中序遍历 inorder = \[9,3,15,20,7\]  
返回如下的二叉树：

![在这里插入图片描述][20200805003057208.png]

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class Solution { 
    
        class TreeNode { 
            int val;
            TreeNode left;
            TreeNode right;
    
            TreeNode(int x) { 
                val = x;
            }
        }
    
        /** * 递归的方法 */
        //利用原理,先序遍历的第一个节点就是根。在中序遍历中通过根 区分哪些是左子树的，哪些是右子树的
        //左右子树，递归
        HashMap<Integer, Integer> map = new HashMap<>();//标记中序遍历
        int[] preorder;//保留的先序遍历
    
        public TreeNode buildTree1(int[] preorder, int[] inorder) { 
            this.preorder = preorder;
            for (int i = 0; i < preorder.length; i++) { 
                map.put(inorder[i], i);
            }
            return recursive(0,0,inorder.length-1);
        }
    
        /** * @param pre_root_idx 先序遍历的索引 * @param in_left_idx 中序遍历的索引 * @param in_right_idx 中序遍历的索引 */
        public TreeNode recursive(int pre_root_idx, int in_left_idx, int in_right_idx) { 
            //相等就是自己
            if (in_left_idx > in_right_idx)
                return null;
    
            //root_idx是在先序里面的
            TreeNode root = new TreeNode(preorder[pre_root_idx]);
            // 有了先序的,再根据先序的，在中序中获 当前根的索引
            int idx = map.get(preorder[pre_root_idx]);
    
            //左子树的根节点就是 左子树的(前序遍历）第一个，就是+1,左边边界就是left，右边边界是中间区分的idx-1
            root.left = recursive(pre_root_idx + 1, in_left_idx, idx - 1);
    
            //由根节点在中序遍历的idx 区分成2段,idx 就是根
    
            //右子树的根，就是右子树（前序遍历）的第一个,就是当前根节点 加上左子树的数量
            // pre_root_idx 当前的根 左子树的长度 = 左子树的左边-右边 (idx-1 - in_left_idx +1) 。最后+1就是右子树的根了
            root.right = recursive(pre_root_idx + (idx-1 - in_left_idx +1)  + 1, idx + 1, in_right_idx);
            return root;
        }
    
        /** * 迭代的方法，用栈取代了递归， 使用前序遍历的第一个元素创建根节点。 创建一个栈，将根节点压入栈内。 初始化中序遍历下标为 0。 遍历前序遍历的每个元素，判断其上一个元素（即栈顶元素）是否等于中序遍历下标指向的元素。 若上一个元素不等于中序遍历下标指向的元素，则将当前元素作为其上一个元素的左子节点，并将当前元素压入栈内。 若上一个元素等于中序遍历下标指向的元素，则从栈内弹出一个元素，同时令中序遍历下标指向下一个元素，之后继续判断栈顶元素是否等于中序遍历下标指向的元素，若相等则重复该操作，直至栈为空或者元素不相等。然后令当前元素为最后一个相等元素的右节点。 遍历结束，返回根节点。 */
    
        public TreeNode buildTree2(int[] preorder, int[] inorder) { 
            if (preorder == null || preorder.length == 0) { 
                return null;
            }
            TreeNode root = new TreeNode(preorder[0]);
            int length = preorder.length;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            int inorderIndex = 0;
            for (int i = 1; i < length; i++) { 
                int preorderVal = preorder[i];
                TreeNode node = stack.peek();
                if (node.val != inorder[inorderIndex]) { 
                    node.left = new TreeNode(preorderVal);
                    stack.push(node.left);
                } else { 
                    while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) { 
                        node = stack.pop();
                        inorderIndex++;
                    }
                    node.right = new TreeNode(preorderVal);
                    stack.push(node.right);
                }
            }
            return root;
        }
    }

[20200805003057208.png]: /images/20230208/b49b1d2a4ebb45c78c4aabe0be61e27a.png