LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal - 题解/Solution

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Given inorder and postorder traversal of a tree, construct the binary tree.
*
* Note: You may assume that duplicates do not exist in the tree.
*
* @author dongyuxi
*
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (null == preorder || null == inorder) {
return null;
}

return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

private TreeNode buildTree(int[] preorder, int pStart, int pEnd,
int[] inorder, int iStart, int iEnd) {
if (iStart > iEnd) {
return null;
}

int rootVal = preorder[pStart];
TreeNode rootNode = new TreeNode(rootVal);
int rootIndex = 0;
while (rootIndex < iEnd - iStart + 1) {
if (inorder[iStart + rootIndex] == rootVal) {
break;
}
rootIndex++;
}
TreeNode leftNode = buildTree(preorder, pStart + 1, pStart + rootIndex, inorder, iStart, iStart + rootIndex - 1);
TreeNode rightNode = buildTree(preorder, pStart + rootIndex + 1, pEnd, inorder, iStart + rootIndex + 1, iEnd);
rootNode.left = leftNode;
rootNode.right = rightNode;

return rootNode;
}
}


支付宝 微信
文章目录