https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
package go.jacob.day807; /** * 106. Construct Binary Tree from Inorder and Postorder Traversal * * @author Jacob * */ public class Demo1 { public TreeNode buildTree(int[] inorder, int[] postorder) { if (inorder == null) return null; return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); } private TreeNode buildTree(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) { if (inLeft > inRight) return null; TreeNode root = new TreeNode(postorder[postRight]); // 只有一个节点，返回root if (inLeft == inRight) return root; int rootNum = 0; for (int i = inLeft; i <= inRight; i++) { if (inorder[i] == postorder[postRight]) { rootNum = i; break; } } int leftLength = rootNum - inLeft; //递归左子树和右子树 root.left = buildTree(inorder, inLeft, inLeft + leftLength - 1, postorder, postLeft, postLeft + leftLength - 1); root.right = buildTree(inorder, inLeft + leftLength + 1, inRight, postorder, postLeft + leftLength, postRight - 1); return root; } }
