I have solved the following LeetCode problem with the same idea in mind. Grab a look:
Problem #106: Construct Binary Tree from Inorder and Postorder Traversal
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if (inorder.length == 0 || postorder.length==0) return null; TreeNode root = treeFromInorderPostorder(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1); return root; } private TreeNode treeFromInorderPostorder(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) { int rootVal = postorder[postEnd]; TreeNode root = new TreeNode(rootVal); int inRootIdx = inStart; for (int i=inStart; i<=inEnd; i++) { if (inorder[i]==rootVal) { inRootIdx = i; break; } } // assert(inRootIdx != -1); int nodesInLeftSubtree = inRootIdx - inStart; if (nodesInLeftSubtree == 0) { root.left = null; } else { root.left = treeFromInorderPostorder(inorder, inStart, inRootIdx-1, postorder, postStart, postStart+nodesInLeftSubtree-1); } int nodesInRightSubtree = inEnd - inRootIdx; if (nodesInRightSubtree == 0) { root.right = null; } else { root.right = treeFromInorderPostorder(inorder, inRootIdx+1, inEnd, postorder, postStart+nodesInLeftSubtree, postEnd-1); } return root; } }
In the similar vein, consider a previously solved problem:
The bounds for parameters with which to make recursive calls in these problems can be slightly tricky to understand so one needs to be careful with those.
Besides that, as always, let me know in comments if you find these solutions helpful or have ideas for improvement.
Toodles!
Toodles!
No comments:
Post a Comment