[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

从前序与中序遍历序列构造二叉树。

题意是给一个二叉树的前序遍历和中序遍历，请根据这两个遍历，把树构造出来。你可以假设树中没有重复的元素。

思路

思路是递归 + 分治。首先，preorder 的首个元素是树的根节点 root。然后在中序遍历中找到这个根节点的位置，在其左边的所有元素会构成其左子树，在其右边的元素会构成其右子树。

还是跑这个例子，

preorder = [3,9,20,15,7] - 3是根节点
inorder = [9,3,15,20,7] - 9是左子树节点；15，20，7会构成右子树

preorder 中，第一个节点 3 是根节点，之后的节点是先列出所有的左孩子，再列出所有的右孩子。在 inorder 的排列中位于 3 之前的所有元素应该是左孩子；位于 3 之后的元素应该是右孩子。代码中的 index 变量，找的是根节点在 inorder 里面的坐标。

根据如上的结论，再下一轮递归调用的时候你会发现 20 是 3 的右孩子，而 15 和 7 分别是 20 的左孩子和右孩子。其他步骤参见代码注释。

复杂度

时间O(n)
空间O(n)

代码

Java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	private TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
		// 递归的第一步：递归终止条件，避免死循环
		if (preStart > preEnd || inStart > inEnd) {
			return null;
		}
		// 重建根节点
		TreeNode root = new TreeNode(preorder[preStart]);
		/*
			index找到根节点在中序遍历的位置
			那么index左边的数都在左子树中，index右边的数都在右子树中，这样就知道了左右子树的大小
		*/
		int index = 0;
		while (inorder[inStart + index] != preorder[preStart]) {
			index++;
		}
		root.left = helper(preorder, preStart + 1, preStart + index, inorder, inStart, inStart + index - 1);
		root.right = helper(preorder, preStart + index + 1, preEnd, inorder, inStart + index + 1, inEnd);
		return root;
	}
}

相关题目

105. Construct Binary Tree from Preorder and Inorder Traversal
106. Construct Binary Tree from Inorder and Postorder Traversal
889. Construct Binary Tree from Preorder and Postorder Traversal
1008. Construct Binary Search Tree from Preorder Traversal