leetcode 105 106 从前序与中序遍历序列构造二叉树 从中序与后序遍历序列构造二叉树

时间:2021-10-30 16:43:31

题目:

105

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

    3
/ \
9 20
/ \
15 7

106

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树:

    3
/ \
9 20
/ \
15 7

思路:

两题思路是相似的,都是通过前序/后序遍历数组确定中间结点,然后找到中间结点在中序遍历的位置。中序遍历序列中,中间结点前的序列就是中间结点的左子树,中间结点后的序列就是中间结点的右子树。按照这样的方法去构建二叉树。

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) {
return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
} private TreeNode build(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd)
return null;
TreeNode root = new TreeNode(preorder[preStart]);
int leftTreeLength = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == preorder[preStart]) //找到左子树上结点的数量
break;
leftTreeLength++;
}
root.left = build(preorder, inorder, preStart + 1, preStart + leftTreeLength, inStart,
inStart + leftTreeLength - 1);
root.right = build(preorder, inorder, preStart + 1 + leftTreeLength, preEnd, inStart + leftTreeLength + 1, inEnd);
return root;
}
}

106

/**
* 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[] inorder, int[] postorder) {
return build(postorder, inorder, 0, postorder.length - 1, 0, inorder.length - 1);
}
private TreeNode build(int[] postorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd)
return null;
TreeNode root = new TreeNode(postorder[preEnd]);
int leftTreeLength = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == postorder[preEnd]) //找到左子树上结点的数量
break;
leftTreeLength++;
}
root.left = build(postorder, inorder, preStart, preStart + leftTreeLength - 1, inStart,
inStart + leftTreeLength - 1);
root.right = build(postorder, inorder, preStart + leftTreeLength, preEnd - 1, inStart + leftTreeLength + 1, inEnd);
return root;
}
}