106, 从中序与后序遍历序列构造二叉树
大约 3 分钟
一、题目描述
给定两个整数数组inorder
和postorder
,其中inorder
是二叉树的中序遍历,postorder
是同一棵树的后序遍历,请你构造并返回这颗二叉树。
示例 1
输入: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
输出: [3, 9, 20, null, null, 15, 7]
示例 2
输入: inorder = [-1], postorder = [-1]
输出: [-1]
提示
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder
和postorder
都由不同的值组成postorder
中每一个值都在inorder
中inorder
保证是树的中序遍历postorder
保证是树的后序遍历
相关主题
- 树
- 数组
- 哈希表
- 分治
- 二叉树
二、题解
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
}
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;
}
}
方法 1: 递归
pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
//Self::recur_1(inorder, postorder)
Self::recur_2(inorder, postorder)
}
fn recur_1(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
const RECUR: fn(&[i32], &[i32]) -> Option<Rc<RefCell<TreeNode>>> = |postorder, inorder| {
let len = postorder.len();
if len == 0 {
return None;
}
let root_val = postorder[len - 1];
let root = Rc::new(RefCell::new(TreeNode::new(root_val)));
if len == 1 {
return Some(root);
}
let mut childs_inorder = inorder.splitn(2, |&v| v == root_val);
let left_inorder = childs_inorder.next().unwrap_or_default();
let right_inorder = childs_inorder.next().unwrap_or_default();
let (left_postorder, right_postorder) = postorder[..len - 1].split_at(left_inorder.len());
root.borrow_mut().left = RECUR(left_postorder, left_inorder);
root.borrow_mut().right = RECUR(right_postorder, right_inorder);
Some(root)
};
RECUR(&postorder, &inorder)
}
fn recur_2(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
let len = postorder.len();
let map = inorder.iter().enumerate()
.fold(HashMap::with_capacity(len), |mut map, (idx, &v)| {
map.insert(v, idx);
map
});
const RECUR: fn(
&[i32], usize, usize, &[i32], usize, usize, &HashMap<i32, usize>,
) -> Option<Rc<RefCell<TreeNode>>> =
|postorder, postorder_l_idx, postorder_r_idx, inorder, inorder_l_idx, inorder_r_idx, map| {
let len = postorder_r_idx - postorder_l_idx;
if len == 0 {
return None;
}
let root_val = postorder[postorder_r_idx - 1];
let root = Rc::new(RefCell::new(TreeNode::new(root_val)));
if len == 1 {
return Some(root);
}
let idx_at_inorder = map[&root_val];
let left_inorder_len = idx_at_inorder - inorder_l_idx;
root.borrow_mut().left = RECUR(
postorder, postorder_l_idx, postorder_l_idx + left_inorder_len,
inorder, inorder_l_idx, idx_at_inorder,
map,
);
root.borrow_mut().right = RECUR(
postorder, postorder_l_idx + left_inorder_len, postorder_r_idx - 1,
inorder, idx_at_inorder + 1, inorder_r_idx,
map,
);
Some(root)
};
RECUR(&postorder, 0, len, &inorder, 0, len, &map)
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
//return this.recur1(inorder, postorder);
return this.recur2(inorder, postorder);
}
BiFunction<List<Integer>, List<Integer>, TreeNode> helper1 = (postorder, inorder) -> {
int size = postorder.size();
if (size == 0) {
return null;
}
Integer rootVal = postorder.getLast();
TreeNode root = new TreeNode(rootVal);
if (size == 1) {
return root;
}
int idxAtInorder = inorder.indexOf(rootVal);
List<Integer> leftInorder = inorder.subList(0, idxAtInorder);
List<Integer> rightInorder = inorder.subList(idxAtInorder + 1, size);
List<Integer> leftPostorder = postorder.subList(0, leftInorder.size());
List<Integer> rightPostorder = postorder.subList(leftInorder.size(), size - 1);
root.left = this.helper1.apply(leftPostorder, leftInorder);
root.right = this.helper1.apply(rightPostorder, rightInorder);
return root;
};
TreeNode recur1(int[] _inorder, int[] _postorder) {
List<Integer> inorder = Arrays.stream(_inorder).boxed().collect(Collectors.toList());
List<Integer> postorder = Arrays.stream(_postorder).boxed().collect(Collectors.toList());
return this.helper1.apply(postorder, inorder);
}
@FunctionalInterface
interface SeptFunction<A, B, C, D, E, F, G, H> {
H apply(A a, B b, C c, D d, E e, F f, G g);
}
SeptFunction<int[], Integer, Integer, int[], Integer, Integer, Map<Integer, Integer>, TreeNode> helper2 =
(postorder, postorderLIdx, postorderRIdx, inorder, inorderLIdx, inorderRIdx, map) -> {
int size = postorderRIdx - postorderLIdx;
if (size == 0) {
return null;
}
int rootVal = postorder[postorderRIdx - 1];
TreeNode root = new TreeNode(rootVal);
if (size == 1) {
return root;
}
int idxAtInorder = map.get(rootVal);
int leftInorderSize = idxAtInorder - inorderLIdx;
root.left = this.helper2.apply(
postorder, postorderLIdx, postorderLIdx + leftInorderSize,
inorder, inorderLIdx, idxAtInorder,
map
);
root.right = this.helper2.apply(
postorder, postorderLIdx + leftInorderSize, postorderRIdx - 1,
inorder, idxAtInorder + 1, inorderRIdx,
map
);
return root;
};
TreeNode recur2(int[] inorder, int[] postorder) {
int size = inorder.length;
Map<Integer, Integer> map = new HashMap<>(size);
for (int i = 0; i < size; i++) {
map.put(inorder[i], i);
}
return this.helper2.apply(postorder, 0, size, inorder, 0, size, map);
}
方法 2: 迭代
pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
Self::iter_1(inorder, postorder)
}
fn iter_1(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
let len = postorder.len();
if len == 0 {
return None;
}
let root = Rc::new(RefCell::new(TreeNode::new(postorder[len - 1])));
let mut stack = vec![root.clone()];
let mut inorder_idx = len - 1;
for postorder_val in postorder.into_iter().rev().skip(1) {
if let Some(last) = stack.last_mut() {
if last.borrow().val != inorder[inorder_idx] {
let right = Rc::new(RefCell::new(TreeNode::new(postorder_val)));
last.borrow_mut().right = Some(right.clone());
stack.push(right);
} else {
let mut last_curr = None;
while let Some(curr) = stack.pop() {
last_curr = Some(curr);
inorder_idx -= 1;
if let Some(last) = stack.last() {
if last.borrow().val != inorder[inorder_idx] {
break;
}
}
}
last_curr.map(|curr| {
let left = Rc::new(RefCell::new(TreeNode::new(postorder_val)));
curr.borrow_mut().left = Some(left.clone());
stack.push(left);
});
}
}
}
Some(root)
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
return this.iter1(inorder, postorder);
}
TreeNode iter1(int[] inorder, int[] postorder) {
int size = postorder.length;
if (size == 0) {
return null;
}
TreeNode root = new TreeNode(postorder[size - 1]);
Deque<TreeNode> stack = new ArrayDeque<>() {{
this.push(root);
}};
int inorderIdx = size - 1;
for (int i = size - 2; i >= 0; i--) {
int postorderVal = postorder[i];
TreeNode top = stack.peek();
if (top.val != inorder[inorderIdx]) {
top.right = new TreeNode(postorderVal);
stack.push(top.right);
} else {
do {
top = stack.pop();
inorderIdx--;
} while (!stack.isEmpty() && stack.peek().val == inorder[inorderIdx]);
top.left = new TreeNode(postorderVal);
stack.push(top.left);
}
}
return root;
}