Leetcode: Construct Binary Tree from Inorder and Postorder Traversal
LeetCode and from Tree Binary Traversal Construct
2023-09-11 14:14:08 时间
Given inorder and postorder traversal of a tree, construct the binary tree.
与Construct Binary Tree from Inorder and Preorder Traversal问题非常类似,唯一区别在于这一次确定root的位置由post traversal来确定,为最后一个元素。
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public TreeNode buildTree(int[] inorder, int[] postorder) { 12 if (inorder.length==0 || postorder.length==0 || inorder.length!=postorder.length) { 13 return null; 14 } 15 int len = inorder.length; 16 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); 17 for (int i=0; i<inorder.length; i++) { 18 map.put(inorder[i], i); 19 } 20 return helper(postorder, 0, len-1, inorder, 0, len-1, map); 21 } 22 23 public TreeNode helper(int[] postorder, int posL, int posR, int[] inorder, int inL, int inR, HashMap<Integer, Integer> map) { 24 if (posL>posR || inL>inR) { 25 return null; 26 } 27 TreeNode root = new TreeNode(postorder[posR]); 28 int index = map.get(postorder[posR]); 29 root.left = helper(postorder, posL, posL+index-1-inL, inorder, inL, index-1, map); 30 root.right = helper(postorder, posL+index-inL, posR-1, inorder, index+1, inR, map); 31 return root; 32 } 33 }
相关文章
- Leetcode 之Count and Say(35)
- Java实现 LeetCode 799 香槟塔 (暴力模拟)
- Java实现 LeetCode 448 找到所有数组中消失的数字
- Java实现 LeetCode 396 旋转函数
- Java实现 LeetCode 347 前 K 个高频元素
- Java实现 LeetCode 106 从中序与后序遍历序列构造二叉树
- Java实现LeetCode_0041_FirstMissingPositive
- 【数组&双指针】LeetCode 1. 两数之和【简单】
- [LeetCode] Bitwise AND of Numbers Range
- [LeetCode] Best Time to Buy and Sell Stock II
- LeetCode-241. 为运算表达式设计优先级【递归】
- LeetCode 121 Best Time to Buy and Sell Stock
- leetcode-WordLadder
- leetcode 121. Best Time to Buy and Sell Stock
- 【Leetcode刷题Python】11. 盛最多水的容器