105. Construct Binary Tree from Preorder and Inorder Traversal 递归构建树

本文主要是介绍105. Construct Binary Tree from Preorder and Inorder Traversal 递归构建树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

已知树的先序和中序遍历结果，构建原树

先序可以确定根节点，在中序遍历中找到与根节点对应的数值的索引，其左侧为左子树 ，右侧为右子树。递归构建；

需要几个参数，先序遍历的起始索引（只确定根节点），中序遍历的起始索引，中序遍历的截止索引（起始到终止索引为子树的范围）

public class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return helper(0,0,preorder.length-1,preorder,inorder);}public TreeNode helper(int prestart,int instart,int inend,int[] preorder,int[]inorder){if(prestart>preorder.length-1||instart>inend) return null;TreeNode root=new TreeNode(preorder[prestart]);int index=0;for(int i=instart;i<=inend;i++){if(root.val==inorder[i])index=i;}root.left=helper(prestart+1,instart,index-1,preorder,inorder);root.right=helper(prestart+index-instart+1,index+1,inend,preorder,inorder);  //prestart+(index-instart)+1  index-instart根据中序确定左子树的节点值，

这样既可确定右子树的位置return root;}
}

中序、后续构建树：

public class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {return conTree(inorder,postorder,0,0,inorder.length-1,postorder.length-1);}public TreeNode conTree(int[] inorder,int[] postorder,int instart,int poststart,int inend,int postend){if (instart > inend) {return null;}int index=0;TreeNode root=new TreeNode(postorder[postend]);for(int i=instart;i<=inend;i++){if(inorder[i]==root.val)index=i;}root.right=conTree(inorder,postorder,index+1,poststart+index-instart,inend,postend-1);root.left=conTree(inorder,postorder,instart,poststart,index-1,poststart+index-instart-1);return root;}}

这篇关于105. Construct Binary Tree from Preorder and Inorder Traversal 递归构建树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---