LeetCode 105. 从前序与中序遍历序列构造二叉树
解法一 递归
思路
前序遍历顺序为 中 - 左 - 右,中序遍历的顺序为 左 - 中 - 右。这意味着前序遍历的第一个元素必为根节点,我们需要在中序遍历中找到这个节点的索引,随后中序遍历数组中这个索引左边的数组是左子树,右边的所有元素是右子树。
代码
/**
* 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) {
if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
return null;
}
return helper(preorder, inorder, 0, 0, inorder.length - 1);
}
private TreeNode helper(int[] preorder, int[] inorder, int preSt, int inSt, int inEnd) {
if (inSt > inEnd || preSt > preorder.length) {
return null;
}
// Set the first value in preorder as root node
TreeNode head = new TreeNode(preorder[preSt]);
// Look for the root node index in inorder traversal
int i = inSt;
while (i <= inEnd) {
if (inorder[i] == preorder[preSt]) {
break;
}
i++;
}
// 设置左子树和右子树。
// 左子树在 preorder 中从根节点后一个数开始(我们只需要这个索引,因为我们只需在 preorder 数组中找到根节点的值)。在 inorder 中左子树从 inSt 到 i - 1 结束。
// 右子树在 preorder 中从左子树结束后的位置开始,为了找到这个索引,我们要根据 inorder 数组计算左子树长度,为 (i - inSt)。在 inorder 中右子树从 i + 1 到 inEnd 结束。
head.left = helper(preorder, inorder, preSt + 1, inSt, i - 1);
head.right = helper(preorder, inorder, preSt + (i - inSt) + 1, i + 1, inEnd);
return head;
}
}
复杂度分析
- 时间复杂度
- O(n)
- 空间复杂度
- O(n)
本作品采用《CC 协议》,转载必须注明作者和本文链接