一、題目描述
給定兩個整數數組?preorder 和 inorder?，其中?preorder 是二叉樹的先序遍歷， inorder?是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。
示例 1:
輸入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 輸出: [3,9,20,null,null,15,7]
示例 2:
輸入: preorder = [-1], inorder = [-1] 輸出: [-1]
提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder?和?inorder?均 無重復 元素inorder?均出現在?preorderpreorder?保證 為二叉樹的前序遍歷序列inorder?保證 為二叉樹的中序遍歷序列
二、解題思路
?這個問題是關于如何根據給定的先序遍歷和中序遍歷數組來重建二叉樹。我們可以使用遞歸方法來解決這個問題。
算法步驟：
- 首先，在先序遍歷數組
preorder中找到根節點的值。 - 然后，在
inorder數組中找到根節點的值，并以此為界將inorder數組分為左右兩部分。 - 遞歸地構造左子樹和右子樹。
- 左子樹的
preorder數組為preorder數組中根節點后面的所有值，左子樹的inorder數組為inorder數組中左子樹部分的所有值。 - 右子樹的
preorder數組為preorder數組中根節點后面的所有值，右子樹的inorder數組為inorder數組中右子樹部分的所有值。 - 重復上述步驟，直到所有節點都被處理。
三、具體代碼
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || inorder == null) {return null;}return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);}private TreeNode helper(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd) {if (preorderStart > preorderEnd || inorderStart > inorderEnd) {return null;}int rootVal = preorder[preorderStart];TreeNode root = new TreeNode(rootVal);int index = inorderStart;while (index <= inorderEnd && inorder[index] != rootVal) {index++;}int leftSubtreeSize = index - inorderStart;int rightSubtreeSize = inorderEnd - index;root.left = helper(preorder, preorderStart + 1, preorderStart + leftSubtreeSize, inorder, inorderStart, index - 1);root.right = helper(preorder, preorderStart + leftSubtreeSize + 1, preorderEnd, inorder, index + 1, inorderEnd);return root;}
}
四、時間復雜度和空間復雜度
1. 時間復雜度
helper?函數對于每個節點都會被調用一次，其中?n?是樹中節點的數量。- 在?
helper?函數內部，對于每個節點，我們都會進行一次數組查找（index?循環），這需要 O(1) 的時間。 - 因此，總的時間復雜度是 O(n)。
2. 空間復雜度
- 空間復雜度主要取決于遞歸調用棧的深度，這通常與樹的高度?
h?有關。 - 在最壞的情況下，樹是完全不平衡的，例如每個節點都只有左子節點或者只有右子節點，此時樹的高度等于節點的數量，空間復雜度為 O(n)。
- 在最好的情況下，樹是完全平衡的，此時樹的高度為?
log(n)，空間復雜度為 O(log(n))。 - 因此，空間復雜度在 O(log(n)) 到 O(n) 之間，取決于樹的形狀。
綜上所述，代碼的時間復雜度是 O(n)，空間復雜度在 O(log(n)) 到 O(n) 之間，取決于樹的形狀。
五、總結知識點
-
遞歸：代碼使用了遞歸的方法來構建二叉樹。遞歸是一種分而治之的算法技巧，將復雜問題分解為更小的子問題，并逐個解決。
-
二叉樹：代碼操作的是二叉樹數據結構，這是一種每個節點最多有兩個子節點的樹形結構。
-
先序遍歷和中序遍歷：先序遍歷是指根節點、左子樹、右子樹的順序，中序遍歷是指左子樹、根節點、右子樹的順序。這兩個遍歷順序是構建二叉樹的關鍵信息來源。
-
數組操作：代碼中使用了數組操作來找到根節點在先序和中序遍歷中的位置，并以此構建左右子樹。
-
函數返回值：
buildTree?函數返回構建的二叉樹的根節點，而?helper?函數返回當前節點的子節點。 -
節點定義：代碼中使用了?
TreeNode?類來定義二叉樹的節點，每個節點包含一個整數值和指向左右子節點的引用。 -
遞歸的基本情況：遞歸函數通常有一個基本情況（base case），即遞歸退出的條件。在這個問題中，基本情況是當?
preorderStart > preorderEnd?或?inorderStart > inorderEnd?時，表示沒有更多的節點可以處理，此時返回?null。 -
類型轉換：在遞歸調用中，
buildTree?函數的返回值被隱式轉換為?TreeNode?類型。 -
遞歸調用棧：遞歸函數的調用會形成調用棧，用于存儲每一層遞歸調用的局部變量和返回地址。
-
樹的高度與深度：在二叉樹中，根節點的深度為1，每個子節點的深度是其父節點深度加1。樹的高度是從根節點到最遠葉子節點的最長路徑上的節點數。
以上就是解決這個問題的詳細步驟，希望能夠為各位提供啟發和幫助。
)
