leetcode 從前序與中序遍歷序列構造二叉樹

題目

給定一棵樹的前序遍歷 preorder 與中序遍歷 inorder。請構造二叉樹並返回其根節點。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均無重複元素
inorder 均出現在 preorder
preorder 保證爲二叉樹的前序遍歷序列
inorder 保證爲二叉樹的中序遍歷序列

參考題解

做這道題目前需要先明白什麼是前序遍歷，什麼是中序遍歷。前序遍歷就是先訪問根節點，接着訪問左子樹，最後訪問右子樹。中序遍歷就是先訪問左子樹，接着訪問根節點，最後訪問右子樹。

根據前序遍歷的特點，可以知道 preorder 數組的第一個元素一定是根節點。根據中序遍歷的特點，可以知道在 inorder 數組中，根節點的左側元素全部都是左子樹的節點，根節點的右側元素全部都是右子樹的節點。

下面給出 Rust 實現代碼：

// 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::cell::RefCell;
use std::rc::Rc;
impl Solution {
  pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    Solution::recursion(&preorder, &inorder)
  }
  fn recursion(preorder: &[i32], inorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
    if preorder.is_empty() || inorder.is_empty() {
      return None;
    }
    // 取出根節點
    let val = preorder[0];
    // 在inorder數組中找到根節點的位置下標
    let idx = inorder.iter().position(|&x| x == val).unwrap();
    // 建立一個節點
    let mut node = TreeNode::new(val);
    // 遞歸構建左子樹
    node.left = Solution::recursion(&preorder[1..idx + 1], &inorder[..idx]);
    // 遞歸構建右子樹
    node.right = Solution::recursion(&preorder[idx + 1..], &inorder[idx + 1..]);
    Some(Rc::new(RefCell::new(node)))
  }
}

上面代碼中，idx 是表示根節點在 inorder 數組中的下標，那 inorder[0] 到 inorder[idx-1] 就都是左子樹的節點，inorder[idx+1] 到 inorder 數組末尾就都是右子樹的節點。左子樹節點的個數就是 idx 個。

Rust 代碼中的 preorder[1..idx + 1] 表示包括 preorder[1]，但不包括 preorder[idx+1]。

題目小結

這道題目初看有點小難度，但是隻要自己寫過了，知道是怎麼回事了，就比較簡單了，代碼實現起來也相對來說比較簡單。代碼的時間複雜度就是數組的元素個數，因爲每個元素只被用來創建了一個節點，只用了一次。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/WU24gruL3gxF_HN5yjuNGQ

猜你喜歡