|
Tough time don't last, tough people do.
没有过不去的坎, 只有打不倒的人。 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树： 限制： 这题和之前讲过的一道题重复了，399，从前序与中序遍历序列构造二叉树，这两道题其实是完全一样的，除了之前讲过的3种方法以外，我们今天再来讲一种解法，这种思想来源于403，验证二叉搜索树的第一种解法。前序遍历的第一个元素肯定是根节点，那么前序遍历的第一个节点在中序位置之前的都是根节点的左子节点，之后的都是根节点的右子节点，我们来简单画个图看一下
这里是随便举个例子，我们看到前序遍历的3肯定是根节点，那么在中序遍历中，3前面的都是3左子节点的值，3后面的都是3右子节点的值， 他真正的结构是这样的
我们来看下代码 1private int in = 0;
2private int pre = 0;
3
4public TreeNode buildTree(int[] preorder, int[] inorder) {
5 return build(preorder, inorder, Integer.MIN_VALUE);
6}
7
8private TreeNode build(int[] preorder, int[] inorder, int stop) {
9 if (pre >= preorder.length)
10 return null;
11 if (inorder[in] == stop) {
12 in++;
13 return null;
14 }
15
16 TreeNode node = new TreeNode(preorder[pre++]);
17 node.left = build(preorder, inorder, node.val);
18 node.right = build(preorder, inorder, stop);
19 return node;
20}
关于二叉树的算法题其实有很多，这里讲的也只是冰山一角，搞懂了上面和前面的几个关于二叉树的题，对二叉树算法相关题的理解也会进一步加深
|
