淄博哪有培训做网站的,网站建设满意度调查问卷,个人作品集网站模板,高端手机网站设计欢迎浏览高耳机的博客 希望我们彼此都有更好的收获 感谢三连支持#xff01; 首先#xff0c;根据先序遍历可以确定根节点E#xff0c;再在中序遍历中通过E确定左树和右数 #xff1b;
设立inBegin和inEnd#xff0c;通过这两个参数的游走#xff0c;来进行子树的创建 首先根据先序遍历可以确定根节点E再在中序遍历中通过E确定左树和右数
设立inBegin和inEnd通过这两个参数的游走来进行子树的创建
已知根节点则左子树的范围表示为inBeginrootIndex - 1
而右子树为rootIndex 1inEnd);
通过递归调用即可不断创建子树直到叶子节点
如果inBegin inEnd,则说明此时为叶子节点应该返回上一层递归
public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChilde(preorder, inorder, 0, inorder.length-1);
}private TreeNode buildTreeChilde(int[] preorder, int[] inorder, int inBegin, int inEnd) {if(inBegin inEnd){return null;}TreeNode root new TreeNode(preorder[preIndex]); // 创建根节点int rootIndex findRootIndex(inorder, inBegin, inEnd, preorder[preIndex]); // 找到根节点在中序遍历中的位置preIndex;root.left buildTreeChilde(preorder, inorder, inBegin, rootIndex-1); // 递归构建左子树root.right buildTreeChilde(preorder, inorder, rootIndex1, inEnd); // 递归构建右子树return root;
}private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key){for (int i inBegin; i inEnd; i) {if (key inorder[i]) {return i;}}return -1;}
OJ链接
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ 同样的根据后序遍历可以确定根节点再在中序遍历中通过根节点确定左树和右数
需要注意的是由于postIndex根据后序遍历左右根创建与前序遍历相反所以每次递归时postIndex--从根节点前的右子树开始递归
同样的已知根节点则右子树表示范围为rootIndex 1inEnd)
而左子树表示为inBeginrootIndex - 1;
通过递归调用即可不断创建子树直到叶子节点
如果inBegin inEnd,则说明此时为叶子节点应该返回上一层递归 public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex postorder.length-1;return buildTreeChilde(inorder, postorder, 0, inorder.length-1);
}private TreeNode buildTreeChilde(int[] inorder, int[] postorder, int inBegin, int inEnd) {if(inBegin inEnd){return null;}TreeNode root new TreeNode(postorder[postIndex]); // 创建根节点int rootIndex findRootIndex(inorder, inBegin, inEnd, postorder[postIndex]); // 找到根节点在中序遍历中的位置postIndex--;root.right buildTreeChilde(inorder, postorder, rootIndex1, inEnd); // 递归构建右子树root.left buildTreeChilde(inorder, postorder, inBegin, rootIndex-1); // 递归构建左子树return root;
}private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key){for (int i inBegin; i inEnd; i) {if (key inorder[i]) {return i;}}return -1;}
OJ链接https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/ 希望这篇博客能为你理解java编程思想提供一些帮助。
如有不足之处请多多指出。
我是高耳机。
