106. 从中序与后序遍历序列构造二叉树

题目描述

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

解题思路

class Solution {
public:
    TreeNode* buildTree(vector<int> ino, vector<int> posto) {
        if(ino.empty())return NULL;
        int l=posto.back();
        auto it=find(ino.begin(),ino.end(),l);
        int i =distance(ino.begin(),it);
        TreeNode*left=buildTree(vector<int>(ino.begin(), it),vector<int>(posto.begin(),posto.begin()+i));
        TreeNode*right=buildTree(vector<int>(it+1,ino.end()),vector<int>(posto.begin()+i,posto.end()-1));
        return new TreeNode(l, left, right);
    }
};

105. 从前序与中序遍历序列构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int> preorder, vector<int>ino) {
        if(ino.empty())return NULL;
        int l =preorder.front();
        auto it=find(ino.begin(),ino.end(),l);
        int i =distance(ino.begin(),it);
        TreeNode*left=buildTree(vector<int>(preorder.begin()+1,preorder.begin()+i+1),vector<int>(ino.begin(), it));
        TreeNode*right=buildTree(vector<int>(preorder.begin()+i+1,preorder.end()),vector<int>(it+1,ino.end()));
        return new TreeNode(l,left,right);
    }
};

学习感想

#![allow(unused)]

fn main() {
// Definition for a binary tree node.
#[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
    }
  }
}
use std::rc::Rc;
use std::cell::RefCell;
struct Solution {}
impl Solution {
    pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Self::build_tree_ref(&inorder, &postorder)
    }

    pub fn build_tree_ref(inorder: &[i32], postorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
        if inorder.len() == 0usize { return None }
        let n: usize = inorder.len();
        let mut num = postorder[n - 1usize];
        let pos: usize = inorder.iter().position(|&x| x == num).unwrap();
        let mut tn: TreeNode = TreeNode::new(num);
        tn.left = Self::build_tree_ref(&inorder[..pos], &postorder[..pos]);
        tn.right = Self::build_tree_ref(&inorder[pos + 1usize .. ], &postorder[pos .. n - 1usize]);
        Some(Rc::new(RefCell::new(tn)))
    }
}
}