根据一棵树的前序遍历与中序遍历构造二叉树
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
示例1：
注意:
你可以假设树中没有重复的元素。例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3 / \ 9 20 / \ 15 7
Java解法
思路：
- 前序遍历，第一个为根节点，第二个为左节点== [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
- 中序遍历，第一个为最左节点，第二个为最左节点父节点 == [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
- 因为没有重复元素，在遍历到值相同时认为是同一节点,采用递归处理
package sj.shimmer.algorithm.m3_2021;
import java.util.Arrays;
import sj.shimmer.algorithm.TreeNode;
/**
* Created by SJ on 2021/3/21.
*/
class D55 {
public static void main(String[] args) {
TreeNode root = buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
System.out.println(root);
}
public static TreeNode buildTree(int[] preorder, int[] inorder) {
//- 前序遍历[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
//- 中序遍历[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
if (preorder == null||preorder.length==0||inorder==null||inorder.length==0) {
return null;
}
int length = inorder.length;
for (int i = 0; i < length; i++) {
if (inorder[i]==preorder[0]) {
TreeNode root = new TreeNode(inorder[i]);
//左子树长度
int left = i;
//前序 左子树
int[] tempLeftP = Arrays.copyOfRange(preorder, 1, left+1);
int[] tempLeftI = Arrays.copyOfRange(inorder, 0, left);
root.left = buildTree(tempLeftP, tempLeftI);
//前序 右子树
int[] tempRightP = Arrays.copyOfRange(preorder, left+1, length);
int[] tempRightI = Arrays.copyOfRange(inorder, left+1, length);
root.right = buildTree(tempRightP, tempRightI);
return root;
}
}
return null;
}
}
image
官方解
-
递归
参考解，主要是找到了递归的条件，思路大致一致，解法效率差不多，都不是很好
image- 时间复杂度：O(n)
- 空间复杂度：O(n)
-
迭代
这个解法较好，属于想到但没想好的
可以看看官方思路
