智能科技 光速东莞网站建设,长春网站开发招聘,微信小程序二维码,北京网站开发摘要
LeetCode第106题要求使用一棵树的中序遍历和后序遍历序列来重建二叉树。本文将介绍两种Java实现方法#xff1a;递归和迭代。
1. 问题描述
给定一棵树的中序遍历和后序遍历序列#xff0c;重建出这棵树的唯一二叉树结构。
2. 示例分析
输入#xff1a;[1,2,4]递归和迭代。
1. 问题描述
给定一棵树的中序遍历和后序遍历序列重建出这棵树的唯一二叉树结构。
2. 示例分析
输入[1,2,4]中序遍历和[4,2,1]后序遍历 输出[2,1,null,null,3]
3. 算法设计
3.1 递归法
递归法利用后序遍历的最后一个元素是树的根节点然后在中序遍历中找到根节点的位置将树分为左右子树。
3.2 迭代法
迭代法使用栈来模拟递归过程通过维护当前遍历的子树的范围逐步构建整棵树。
4. Java代码实现
4.1 递归法
class Solution {MapInteger, Integer map; // 方便根据数值查找位置public TreeNode buildTree(int[] inorder, int[] postorder) {map new HashMap();for (int i 0; i inorder.length; i) { // 用map保存中序序列的数值对应位置map.put(inorder[i], i);}return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开}public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {// 参数里的范围都是前闭后开if (inBegin inEnd || postBegin postEnd) { // 不满足左闭右开说明没有元素返回空树return null;}int rootIndex map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置TreeNode root new TreeNode(inorder[rootIndex]); // 构造结点int lenOfLeft rootIndex - inBegin; // 保存中序左子树个数用来确定后序数列的个数root.left findNode(inorder, inBegin, rootIndex,postorder, postBegin, postBegin lenOfLeft);root.right findNode(inorder, rootIndex 1, inEnd,postorder, postBegin lenOfLeft, postEnd - 1);return root;}
}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val x; }
}4.2 迭代法
public class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder null || postorder null || inorder.length ! postorder.length) {return null;}TreeNode[] nodes new TreeNode[inorder.length];for (int i 0; i inorder.length; i) {nodes[i] new TreeNode(inorder[i]);}ArrayDequeTreeNode stack new ArrayDeque();TreeNode root nodes[postorder.length - 1];stack.push(root);int postIndex postorder.length - 2;for (int i inorder.length - 2; i 0; i--) {TreeNode node nodes[i];while (!stack.isEmpty() stack.peek().val node.val) {node.left stack.pop();}stack.push(node);postIndex--;}return root;}
}5. 代码解析
递归法通过递归调用buildTreeHelper方法利用后序遍历的最后一个元素作为根节点然后在中序遍历中找到根节点的位置递归地构建左右子树。迭代法使用栈来模拟递归过程从后序遍历的最后一个元素开始逐步构建整棵树。
6. 测试验证
使用LeetCode平台或其他测试工具对提供的代码进行测试确保算法的正确性。
7. 总结
LeetCode第106题是一个典型的树重建问题通过理解二叉树的遍历特性可以有效地利用中序和后序遍历序列重建二叉树。递归法直观易理解而迭代法则更节省空间。
8. 参考文献
LeetCode第106题官方题解二叉树遍历
