题目与示例
106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] inOrder, int[] postOrder) {
// 递归出口
if (inOrder.length == 0 || postOrder.length == 0) return null;
// 在前序结果中 找到根节点
int rootValue = postOrder[postOrder.length - 1];
TreeNode root = new TreeNode(rootValue);
// 查找根节点在中序结果中的位置
int leftSize = find(inOrder, rootValue);
// 切分出左子树的中序和后序结果
// 使用 Arrays.copyOfRange方法 三个参数 原始数组 起始位置 终止位置
// [起始位置,终止位置)
//
// 3 4 5 [0,leftSize)
// 4 3 2 [0,leftSize)
int[] leftInOrder = Arrays.copyOfRange(inOrder, 0, leftSize);
int[] leftPostOrder = Arrays.copyOfRange(postOrder, 0, leftSize);
root.left = buildTree(leftInOrder, leftPostOrder);
// 切分出右子树的中序和后序结果
//
// 5 [leftSize+1,end)
// 5 [leftSize,end-1)
int[] rightInOrder = Arrays.copyOfRange(inOrder, leftSize + 1, inOrder.length);
int[] rightPostOrder = Arrays.copyOfRange(postOrder, leftSize, postOrder.length - 1);
root.right = buildTree(rightInOrder, rightPostOrder);
return root;
}
int find(int[] arr,int val){
for(int i=0;i<arr.length;i++){
if(arr[i] == val) return i;
}
return -1;
}
}