网站性能优化方法,电商网站建设的维护要多少钱,乡村旅游网站的建设分析,长沙专业建网站给定两个整数数组 inorder 和 postorder #xff0c;其中 inorder 是二叉树的中序遍历#xff0c; postorder 是同一棵树的后序遍历#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入#xff1a;inorder [9,3,15,20,7], postorder [9,15,7,20,3]
输出#xff1a;[3…给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例 1: 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3]
输出[3,9,20,null,null,15,7]示例 2:
输入inorder [-1], postorder [-1]
输出[-1]解法一
常规解法利用递归传递左子树和右子树的数组范围即可。
public TreeNode buildTree(int[] inorder, int[] postorder) {HashMapInteger, Integer map new HashMap();for (int i 0; i inorder.length; i) {map.put(inorder[i], i);}return buildTreeHelper(inorder, 0, inorder.length, postorder, 0, postorder.length, map);
}private TreeNode buildTreeHelper(int[] inorder, int i_start, int i_end, int[] postorder, int p_start, int p_end,HashMapInteger, Integer map) {if (p_start p_end) {return null;}int root_val postorder[p_end - 1];TreeNode root new TreeNode(root_val);int i_root_index map.get(root_val);int leftNum i_root_index - i_start;root.left buildTreeHelper(inorder, i_start, i_root_index, postorder, p_start, p_start leftNum, map);root.right buildTreeHelper(inorder, i_root_index 1, i_end, postorder, p_start leftNum, p_end - 1,map);return root;
}解法二 stop 值
这里的话之前说了递归的话得先构造右子树再构造左子树此外各种指针也应该从末尾向零走。
视线从右往左看。 3/ \9 20/ \15 7s 初始化一个树中所有的数字都不会相等的数所以代码中用了一个 long 来表示
------------------
中序9, 3, 15, 20, 7
^ ^
s i后序
9, 15, 7, 20, 3^ p
-------------------p 和 i 都从右往左进行遍历所以 p 开始产生的每次都是右子树的根节点。之前代码里的要相应的改成--。
int post;
int in;
public TreeNode buildTree(int[] inorder, int[] postorder) {post postorder.length - 1;in inorder.length - 1;return buildTreeHelper(inorder, postorder, (long) Integer.MIN_VALUE - 1);
}private TreeNode buildTreeHelper(int[] inorder, int[] postorder, long stop) {if (post -1) {return null;}if (inorder[in] stop) {in--;return null;}int root_val postorder[post--];TreeNode root new TreeNode(root_val);root.right buildTreeHelper(inorder, postorder, root_val);root.left buildTreeHelper(inorder, postorder, stop);return root;
}解法三 栈
之前解法是构造左子树、左子树、左子树出现相等构造一颗右子树。这里相应的要改成构造右子树、右子树、右子树出现相等构造一颗左子树。和解法二一样两个指针的话也是从末尾到头部进行。
public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder.length 0) {return null;}StackTreeNode roots new StackTreeNode();int post postorder.length - 1;int in inorder.length - 1;TreeNode curRoot new TreeNode(postorder[post]);TreeNode root curRoot;roots.push(curRoot);post--;while (post 0) {if (curRoot.val inorder[in]) {while (!roots.isEmpty() roots.peek().val inorder[in]) {curRoot roots.peek();roots.pop();in--;}curRoot.left new TreeNode(postorder[post]);curRoot curRoot.left;roots.push(curRoot);post--;} else {curRoot.right new TreeNode(postorder[post]);curRoot curRoot.right;roots.push(curRoot);post--;}}return root;
}
