一、题目概述
二、思路方向
在Java中,根据给定的中序遍历(inorder)和后序遍历(postorder)数组来构造二叉树是一个相对常见的问题。基本思路是,后序遍历的最后一个元素总是当前子树的根节点。然后,在中序遍历中找到这个根节点的位置,它将中序遍历分为左子树和右子树。接下来,我们可以递归地构建左子树和右子树。
具体的步骤:
递归基:如果中序遍历或后序遍历数组为空,则返回null,表示空树。
找到根节点:后序遍历数组的最后一个元素是当前子树的根节点。
分割中序遍历:在中序遍历中找到根节点的位置,它将中序遍历分为左子树和右子树的部分。
递归构建子树:使用分割后的中序遍历数组和后序遍历数组(去掉最后一个元素,即根节点)来递归构建左子树和右子树。
创建并连接节点:使用根节点值创建新的树节点,并将递归构建的左子树和右子树连接到该节点上。
三、代码实现
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }
} public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if (inorder == null || postorder == null || inorder.length != postorder.length) { return null; } return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); } private TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) { if (inStart > inEnd || postStart > postEnd) { return null; } // 后序遍历的最后一个元素是根节点 int rootVal = postorder[postEnd]; TreeNode root = new TreeNode(rootVal); // 在中序遍历中找到根节点的位置 int rootIndexInorder = inStart; while (inorder[rootIndexInorder] != rootVal) { rootIndexInorder++; } // 递归构建左子树和右子树 int leftSubtreeSize = rootIndexInorder - inStart; root.left = buildTreeHelper(inorder, inStart, rootIndexInorder - 1, postorder, postStart, postStart + leftSubtreeSize - 1); root.right = buildTreeHelper(inorder, rootIndexInorder + 1, inEnd, postorder, postStart + leftSubtreeSize, postEnd - 1); return root; }
}
执行结果:
四、小结
这段代码首先检查输入数组的有效性,然后调用
buildTreeHelper
方法进行递归构建。在buildTreeHelper
方法中,首先检查递归的终止条件(即子数组为空时),然后找到后序遍历的最后一个元素作为根节点,并在中序遍历中找到该根节点的位置,以此分割中序遍历数组。最后,递归地构建左子树和右子树,并将它们连接到根节点上。
结语
宁恋本乡一捻土
莫爱他乡万两金
!!!