如何根据前序遍历和中序遍历，或者中序遍历和后序遍历创建二叉树？大致思路如下文章；
分析：
代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int preIndex;
public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegan, int inEnd){
//如果ib > ie说明递归终止
if(inBegan > inEnd){
return null;
}
//创建根节点
TreeNode root = new TreeNode(preorder[preIndex]);
//在中序遍历中找到对应的根节点下标
int InorderIndex = fundInorderIndex(inorder, preorder[preIndex], inBegan, inEnd);
//前序遍历中的下标继续往后遍历
preIndex++;
//通过递归继续创建左子树和右子树
root.left = buildTreeChild(preorder, inorder, inBegan, InorderIndex - 1);
root.right = buildTreeChild(preorder, inorder, InorderIndex + 1, inEnd);
//最后返回根结点即可
return root;
}
public int fundInorderIndex(int[] inorder, int val, int inBegan, int inEnd){
for(int i = inBegan; i <= inEnd; i++){
if(inorder[i] == val){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
}
}
分析：
和前序与中序遍历的思路一样，但是注意的是，后序遍历中是从后向前找根结点，因此，当你写出后序遍历的顺序的时候，会发现需要先创建右子树，再创建左子树。
代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int preIndex;
public TreeNode buildTreeChild(int[] postorder, int[] inorder, int inBegan, int inEnd){
//如果ib > ie说明递归终止
if(inBegan > inEnd){
return null;
}
//创建根节点
TreeNode root = new TreeNode(postorder[preIndex]);
//在中序遍历中找到对应的根节点下标
int InorderIndex = fundInorderIndex(inorder, postorder[preIndex], inBegan, inEnd);
//前序遍历中的下标继续往后遍历
preIndex--;
//这里要注意，先构建左树再构建右树！
root.right = buildTreeChild(postorder, inorder, InorderIndex + 1, inEnd);
root.left = buildTreeChild(postorder, inorder, inBegan, InorderIndex - 1);
//最后返回根结点即可
return root;
}
public int fundInorderIndex(int[] inorder, int val, int inBegan, int inEnd){
for(int i = inBegan; i <= inEnd; i++){
if(inorder[i] == val){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
preIndex = postorder.length - 1;
return buildTreeChild(postorder, inorder, 0, inorder.length - 1);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/130463.html
