本文主要是介绍leetcode刷题(97)——105. 从前序与中序遍历序列构造二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3/ \9 20/ \15 7
1.先回顾前序遍历和中序遍历的框架:
void traverse(TreeNode root) {// 前序遍历preorder.add(root.val);traverse(root.left);traverse(root.right);
}void traverse(TreeNode root) {traverse(root.left);// 中序遍历inorder.add(root.val);traverse(root.right);
}
通过上面的图观察规律,前序遍历第一个值肯定是根结点,中序遍历,根结点左边都是左子树,右边都是右子树
对于preorder数组呢?如何确定左右数组对应的起始索引和终止索引?
这个可以通过左子树的节点数推导出来,假设左子树的节点数为leftSize,那么preorder数组上的索引情况是这样的:
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return helpBuild(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}private TreeNode helpBuild(int[] preorder,int preStart,int preEnd,int[] inorder,int inorderStart,int inordorEnd){if(preStart>preEnd){return null;}int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);int index = 0;for(int i=0;i<=inordorEnd;i++){if(rootVal == inorder[i]){index = i;break;}}int leftSize = index - inorderStart;root.left = helpBuild(preorder,preStart+1,preStart+leftSize,inorder,inorderStart,index-1);root.right = helpBuild(preorder,preStart+leftSize+1,preEnd,inorder,index+1,inordorEnd);return root;}
}
这篇关于leetcode刷题(97)——105. 从前序与中序遍历序列构造二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!