【数据结构】从前序与中序遍历，或中序与后序遍历序列，构造二叉树

欢迎浏览高耳机的博客

希望我们彼此都有更好的收获

感谢三连支持！

 

首先，根据先序遍历可以确定根节点E，再在中序遍历中通过E确定左树和右数 ；

设立inBegin和inEnd，通过这两个参数的游走，来进行子树的创建；

已知根节点，则左子树的范围表示为（inBegin，rootIndex - 1）；

而右子树为（rootIndex + 1，inEnd);

通过递归调用，即可不断创建子树，直到叶子节点；

如果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, rootIndex+1, 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 + 1，inEnd)；

而左子树表示为（inBegin，rootIndex - 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, rootIndex+1, 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编程思想提供一些帮助。

如有不足之处请多多指出。

我是高耳机。