题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如,给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:
限制:
0 <= 节点个数 <= 5000
解题思路 方法一:递归
根据前序和中序的关系进行遍历。
前序遍历的顺序:根结点,左孩子结点,右孩子结点
中序遍历的顺序:左孩子结点,根节点,右孩子结点
所有我们需要做的是:在中序遍历结果中找到根节点的所在位置,将中序遍历结果分为三部分(左,根,右)。
根据中序遍历结果的长度,进而可以把前序遍历结果也分为三个部分(根,左,右)。
递归调用,直到当前数组长度为0,返回结果。
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public TreeNode buildTree (int [] preorder, int [] inorder) { int preleft = 0 , preright = preorder.length - 1 ; int inleft = 0 , inright = inorder.length - 1 ; return createTree(preorder, inorder, preleft, preright, inleft, inright); } TreeNode createTree (int [] preorder, int [] inorder, int preleft, int preright, int inleft, int inright) { if (preleft > preright || inleft > inright) { return null ; } TreeNode root = new TreeNode(preorder[preleft]); int inIndex = inleft; for (int i = inleft; i <= inright; i++) { if (inorder[i] == preorder[preleft]) { inIndex = i; } } root.left = createTree(preorder, inorder, preleft + 1 , preleft + inIndex - inleft, inleft, inIndex - 1 ); root.right = createTree(preorder, inorder, preleft + inIndex - inleft + 1 , preright, inIndex + 1 , inright); return root; }
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n) 递归调用为O(h),h为二叉树的高度、返回结果O(n).因为h<n,所以总的空间复杂度为O(n).
方法二:递归+优化
在方法一的基础上,进行优化查找中序遍历中的根结点方法,利用map集合存储中序队列值与下标对应关系。
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Map<Integer,Integer> map=new HashMap<>(); public TreeNode buildTree2 (int [] preorder, int [] inorder) { int preleft = 0 , preright = preorder.length - 1 ; int inleft = 0 , inright = inorder.length - 1 ; for (int i=0 ;i<inorder.length;i++){ map.put(inorder[i],i); } return createTree2(preorder, inorder, preleft, preright, inleft, inright); } TreeNode createTree2 (int [] preorder, int [] inorder, int preleft, int preright, int inleft, int inright) { if (preleft > preright || inleft > inright) { return null ; } TreeNode root = new TreeNode(preorder[preleft]); int inIndex=map.get(preorder[preleft]); root.left = createTree(preorder, inorder, preleft + 1 , preleft + inIndex - inleft, inleft, inIndex - 1 ); root.right = createTree(preorder, inorder, preleft + inIndex - inleft + 1 , preright, inIndex + 1 , inright); return root; }
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n) 递归调用为O(h),h为二叉树的高度、返回结果O(n).因为h<n,所以总的空间复杂度为O(n).
方法三:迭代
我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点(前序遍历的第一个节点),指针指向中序遍历的第一个节点;我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点, 那么我们不断地弹出栈顶节点并向右移动 index,并将当前节点作为最后一个弹出的节点的右儿子; 如果 index 和栈顶节点不同,我们将当前节点作为栈顶节点的左儿子; 无论是哪一种情况,我们最后都将当前的节点入栈。
代码实现: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public TreeNode buildTree3 (int [] preorder, int [] inorder) { if (preorder.length == 0 || preorder.length == 0 ) { return null ; } TreeNode root = new TreeNode(preorder[0 ]); Deque<TreeNode> stack = new LinkedList<TreeNode>(); stack.push(root); int inorderIndex = 0 ; for (int i = 1 ; i < preorder.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; }
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n) 递归调用为O(h),h为二叉树的高度、返回结果O(n).因为h<n,所以总的空间复杂度为O(n).
资源: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-by-leetcode-s/