自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

從前序及中序與后序遍歷序列構造二叉樹登場！

作者：程序員Carl
開發(fā) 前端
首先回憶一下如何根據兩個順序構造一個唯一的二叉樹，相信理論知識大家應該都清楚，就是以 后序數組的最后一個元素為切割點，先切中序數組，根據中序數組，反過來在切后序數組。

[[418044]]

看完本文，可以一起解決如下兩道題目

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

從中序與后序遍歷序列構造二叉樹題

目地址：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

根據一棵樹的中序遍歷與后序遍歷構造二叉樹。

注意: 你可以假設樹中沒有重復的元素。

例如，給出

中序遍歷 inorder = [9,3,15,20,7] 后序遍歷 postorder = [9,15,7,20,3] 返回如下的二叉樹：

圖片

思路

首先回憶一下如何根據兩個順序構造一個唯一的二叉樹，相信理論知識大家應該都清楚，就是以 后序數組的最后一個元素為切割點，先切中序數組，根據中序數組，反過來在切后序數組。一層一層切下去，每次后序數組最后一個元素就是節(jié)點元素。

如果讓我們肉眼看兩個序列，畫一顆二叉樹的話，應該分分鐘都可以畫出來。

流程如圖：

圖片

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

那么代碼應該怎么寫呢?

說到一層一層切割，就應該想到了遞歸。

來看一下一共分幾步：

  • 第一步：如果數組大小為零的話，說明是空節(jié)點了。
  • 第二步：如果不為空，那么取后序數組最后一個元素作為節(jié)點元素。
  • 第三步：找到后序數組最后一個元素在中序數組的位置，作為切割點
  • 第四步：切割中序數組，切成中序左數組和中序右數組 (順序別搞反了，一定是先切中序數組)
  • 第五步：切割后序數組，切成后序左數組和后序右數組
  • 第六步：遞歸處理左區(qū)間和右區(qū)間

不難寫出如下代碼：(先把框架寫出來)

  1. TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) { 
  2.  
  3.     // 第一步 
  4.     if (postorder.size() == 0) return NULL; 
  5.  
  6.     // 第二步：后序遍歷數組最后一個元素，就是當前的中間節(jié)點 
  7.     int rootValue = postorder[postorder.size() - 1]; 
  8.     TreeNode* root = new TreeNode(rootValue); 
  9.  
  10.     // 葉子節(jié)點 
  11.     if (postorder.size() == 1) return root; 
  12.  
  13.     // 第三步：找切割點 
  14.     int delimiterIndex; 
  15.     for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) { 
  16.         if (inorder[delimiterIndex] == rootValue) break; 
  17.     } 
  18.  
  19.     // 第四步：切割中序數組，得到 中序左數組和中序右數組 
  20.     // 第五步：切割后序數組，得到 后序左數組和后序右數組 
  21.  
  22.     // 第六步 
  23.     root->left = traversal(中序左數組, 后序左數組); 
  24.     root->right = traversal(中序右數組, 后序右數組); 
  25.  
  26.     return root; 
  27. } 

難點大家應該發(fā)現了，就是如何切割，以及邊界值找不好很容易亂套。

此時應該注意確定切割的標準，是左閉右開，還有左開又閉，還是左閉又閉，這個就是不變量，要在遞歸中保持這個不變量。

在切割的過程中會產生四個區(qū)間，把握不好不變量的話，一會左閉右開，一會左閉又閉，必然亂套!

我在704.二分查找和59.螺旋矩陣II中都強調過循環(huán)不變量的重要性，在二分查找以及螺旋矩陣的求解中，堅持循環(huán)不變量非常重要，本題也是。

首先要切割中序數組，為什么先切割中序數組呢?

切割點在后序數組的最后一個元素，就是用這個元素來切割中序數組的，所以必要先切割中序數組。

中序數組相對比較好切，找到切割點(后序數組的最后一個元素)在中序數組的位置，然后切割，如下代碼中我堅持左閉右開的原則：

  1. // 找到中序遍歷的切割點 
  2. int delimiterIndex; 
  3. for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) { 
  4.     if (inorder[delimiterIndex] == rootValue) break; 
  5. } 
  6.  
  7. // 左閉右開區(qū)間：[0, delimiterIndex) 
  8. vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex); 
  9. // [delimiterIndex + 1, end) 
  10. vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() ); 

接下來就要切割后序數組了。

首先后序數組的最后一個元素指定不能要了，這是切割點 也是 當前二叉樹中間節(jié)點的元素，已經用了。

后序數組的切割點怎么找?

后序數組沒有明確的切割元素來進行左右切割，不像中序數組有明確的切割點，切割點左右分開就可以了。

此時有一個很重的點，就是中序數組大小一定是和后序數組的大小相同的(這是必然)。

中序數組我們都切成了左中序數組和右中序數組了，那么后序數組就可以按照左中序數組的大小來切割，切成左后序數組和右后序數組。

代碼如下：

  1. // postorder 舍棄末尾元素，因為這個元素就是中間節(jié)點，已經用過了 
  2. postorder.resize(postorder.size() - 1); 
  3.  
  4. // 左閉右開，注意這里使用了左中序數組大小作為切割點：[0, leftInorder.size) 
  5. vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size()); 
  6. // [leftInorder.size(), end) 
  7. vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end()); 

此時，中序數組切成了左中序數組和右中序數組，后序數組切割成左后序數組和右后序數組。

接下來可以遞歸了，代碼如下：

  1. root->left = traversal(leftInorder, leftPostorder); 
  2. root->right = traversal(rightInorder, rightPostorder); 

完整代碼如下：

C++完整代碼

  1. class Solution { 
  2. private: 
  3.     TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) { 
  4.         if (postorder.size() == 0) return NULL; 
  5.  
  6.         // 后序遍歷數組最后一個元素，就是當前的中間節(jié)點 
  7.         int rootValue = postorder[postorder.size() - 1]; 
  8.         TreeNode* root = new TreeNode(rootValue); 
  9.  
  10.         // 葉子節(jié)點 
  11.         if (postorder.size() == 1) return root; 
  12.  
  13.         // 找到中序遍歷的切割點 
  14.         int delimiterIndex; 
  15.         for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) { 
  16.             if (inorder[delimiterIndex] == rootValue) break; 
  17.         } 
  18.  
  19.         // 切割中序數組 
  20.         // 左閉右開區(qū)間：[0, delimiterIndex) 
  21.         vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex); 
  22.         // [delimiterIndex + 1, end) 
  23.         vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() ); 
  24.  
  25.         // postorder 舍棄末尾元素 
  26.         postorder.resize(postorder.size() - 1); 
  27.  
  28.         // 切割后序數組 
  29.         // 依然左閉右開，注意這里使用了左中序數組大小作為切割點 
  30.         // [0, leftInorder.size) 
  31.         vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size()); 
  32.         // [leftInorder.size(), end) 
  33.         vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end()); 
  34.  
  35.         root->left = traversal(leftInorder, leftPostorder); 
  36.         root->right = traversal(rightInorder, rightPostorder); 
  37.  
  38.         return root; 
  39.     } 
  40. public: 
  41.     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { 
  42.         if (inorder.size() == 0 || postorder.size() == 0) return NULL; 
  43.         return traversal(inorder, postorder); 
  44.     } 
  45. }; 

相信大家自己就算是思路清晰， 代碼寫出來一定是各種問題，所以一定要加日志來調試，看看是不是按照自己思路來切割的，不要大腦模擬，那樣越想越糊涂。

下面給出用下表索引寫出的代碼版本：(思路是一樣的，只不過不用重復定義vector了，每次用下表索引來分割)

C++優(yōu)化版本

那么這個版本寫出來依然要打日志進行調試，打日志的版本如下：(該版本不要在leetcode上提交，容易超時)

  1. class Solution { 
  2. private: 
  3.     TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) { 
  4.         if (postorderBegin == postorderEnd) return NULL; 
  5.  
  6.         int rootValue = postorder[postorderEnd - 1]; 
  7.         TreeNode* root = new TreeNode(rootValue); 
  8.  
  9.         if (postorderEnd - postorderBegin == 1) return root; 
  10.  
  11.         int delimiterIndex; 
  12.         for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) { 
  13.             if (inorder[delimiterIndex] == rootValue) break; 
  14.         } 
  15.         // 切割中序數組 
  16.         // 左中序區(qū)間，左閉右開[leftInorderBegin, leftInorderEnd) 
  17.         int leftInorderBegin = inorderBegin; 
  18.         int leftInorderEnd = delimiterIndex; 
  19.         // 右中序區(qū)間，左閉右開[rightInorderBegin, rightInorderEnd) 
  20.         int rightInorderBegin = delimiterIndex + 1; 
  21.         int rightInorderEnd = inorderEnd; 
  22.  
  23.         // 切割后序數組 
  24.         // 左后序區(qū)間，左閉右開[leftPostorderBegin, leftPostorderEnd) 
  25.         int leftPostorderBegin =  postorderBegin; 
  26.         int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 終止位置是 需要加上 中序區(qū)間的大小size 
  27.         // 右后序區(qū)間，左閉右開[rightPostorderBegin, rightPostorderEnd) 
  28.         int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin); 
  29.         int rightPostorderEnd = postorderEnd - 1; // 排除最后一個元素，已經作為節(jié)點了 
  30.  
  31.         cout << "----------" << endl; 
  32.         cout << "leftInorder :"; 
  33.         for (int i = leftInorderBegin; i < leftInorderEnd; i++) { 
  34.             cout << inorder[i] << " "; 
  35.         } 
  36.         cout << endl; 
  37.  
  38.         cout << "rightInorder :"; 
  39.         for (int i = rightInorderBegin; i < rightInorderEnd; i++) { 
  40.             cout << inorder[i] << " "; 
  41.         } 
  42.         cout << endl; 
  43.  
  44.         cout << "leftpostorder :"; 
  45.         for (int i = leftPostorderBegin; i < leftPostorderEnd; i++) { 
  46.             cout << postorder[i] << " "; 
  47.         } 
  48.         cout << endl; 
  49.  
  50.         cout << "rightpostorder :"; 
  51.         for (int i = rightPostorderBegin; i < rightPostorderEnd; i++) { 
  52.             cout << postorder[i] << " "; 
  53.         } 
  54.         cout << endl; 
  55.  
  56.         root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd); 
  57.         root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd); 
  58.  
  59.         return root; 
  60.     } 
  61. public: 
  62.     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { 
  63.         if (inorder.size() == 0 || postorder.size() == 0) return NULL; 
  64.         return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size()); 
  65.     } 
  66. }; 

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

題目地址：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

根據一棵樹的前序遍歷與中序遍歷構造二叉樹。

注意: 你可以假設樹中沒有重復的元素。

例如，給出

前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7] 返回如下的二叉樹：

圖片

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

思路

本題和106是一樣的道理。

我就直接給出代碼了。

  1. class Solution { 
  2. private: 
  3.         TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) { 
  4.         if (preorderBegin == preorderEnd) return NULL; 
  5.  
  6.         int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0 
  7.         TreeNode* root = new TreeNode(rootValue); 
  8.  
  9.         if (preorderEnd - preorderBegin == 1) return root; 
  10.  
  11.         int delimiterIndex; 
  12.         for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) { 
  13.             if (inorder[delimiterIndex] == rootValue) break; 
  14.         } 
  15.         // 切割中序數組 
  16.         // 中序左區(qū)間，左閉右開[leftInorderBegin, leftInorderEnd) 
  17.         int leftInorderBegin = inorderBegin; 
  18.         int leftInorderEnd = delimiterIndex; 
  19.         // 中序右區(qū)間，左閉右開[rightInorderBegin, rightInorderEnd) 
  20.         int rightInorderBegin = delimiterIndex + 1; 
  21.         int rightInorderEnd = inorderEnd; 
  22.  
  23.         // 切割前序數組 
  24.         // 前序左區(qū)間，左閉右開[leftPreorderBegin, leftPreorderEnd) 
  25.         int leftPreorderBegin =  preorderBegin + 1; 
  26.         int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 終止位置是起始位置加上中序左區(qū)間的大小size 
  27.         // 前序右區(qū)間, 左閉右開[rightPreorderBegin, rightPreorderEnd) 
  28.         int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin); 
  29.         int rightPreorderEnd = preorderEnd; 
  30.  
  31.         root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  preorder, leftPreorderBegin, leftPreorderEnd); 
  32.         root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd); 
  33.  
  34.         return root; 
  35.     } 
  36.  
  37. public: 
  38.     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
  39.         if (inorder.size() == 0 || preorder.size() == 0) return NULL; 
  40.  
  41.         // 參數堅持左閉右開的原則 
  42.         return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size()); 
  43.     } 
  44. }; 

思考題

前序和中序可以唯一確定一顆二叉樹。

后序和中序可以唯一確定一顆二叉樹。

那么前序和后序可不可以唯一確定一顆二叉樹呢?

前序和后序不能唯一確定一顆二叉樹!，因為沒有中序遍歷無法確定左右部分，也就是無法分割。

舉一個例子：

圖片

從中序與后序遍歷序列構造二叉樹2

tree1 的前序遍歷是[1 2 3]， 后序遍歷是[3 2 1]。

tree2 的前序遍歷是[1 2 3]， 后序遍歷是[3 2 1]。

那么tree1 和 tree2 的前序和后序完全相同，這是一棵樹么，很明顯是兩棵樹!

所以前序和后序不能唯一確定一顆二叉樹!

總結

之前我們講的二叉樹題目都是各種遍歷二叉樹，這次開始構造二叉樹了，思路其實比較簡單，但是真正代碼實現出來并不容易。

所以要避免眼高手低，踏實的把代碼寫出來。

我同時給出了添加日志的代碼版本，因為這種題目是不太容易寫出來調一調就能過的，所以一定要把流程日志打出來，看看符不符合自己的思路。

大家遇到這種題目的時候，也要學會打日志來調試(如何打日志有時候也是個技術活)，不要腦動模擬，腦動模擬很容易越想越亂。

最后我還給出了為什么前序和中序可以唯一確定一顆二叉樹，后序和中序可以唯一確定一顆二叉樹，而前序和后序卻不行。

認真研究完本篇，相信大家對二叉樹的構造會清晰很多。

其他語言版本

Java

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

  1. class Solution { 
  2.     public TreeNode buildTree(int[] inorder, int[] postorder) { 
  3.         return buildTree1(inorder, 0, inorder.length, postorder, 0, postorder.length); 
  4.     } 
  5.     public TreeNode buildTree1(int[] inorder, int inLeft, int inRight, 
  6.                                int[] postorder, int postLeft, int postRight) { 
  7.         // 沒有元素了 
  8.         if (inRight - inLeft < 1) { 
  9.             return null; 
  10.         } 
  11.         // 只有一個元素了 
  12.         if (inRight - inLeft == 1) { 
  13.             return new TreeNode(inorder[inLeft]); 
  14.         } 
  15.         // 后序數組postorder里最后一個即為根結點 
  16.         int rootVal = postorder[postRight - 1]; 
  17.         TreeNode root = new TreeNode(rootVal); 
  18.         int rootIndex = 0; 
  19.         // 根據根結點的值找到該值在中序數組inorder里的位置 
  20.         for (int i = inLeft; i < inRight; i++) { 
  21.             if (inorder[i] == rootVal) { 
  22.                 rootIndex = i; 
  23.             } 
  24.         } 
  25.         // 根據rootIndex劃分左右子樹 
  26.         root.left = buildTree1(inorder, inLeft, rootIndex, 
  27.                 postorder, postLeft, postLeft + (rootIndex - inLeft)); 
  28.         root.right = buildTree1(inorder, rootIndex + 1, inRight, 
  29.                 postorder, postLeft + (rootIndex - inLeft), postRight - 1); 
  30.         return root; 
  31.     } 
  32. } 

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

  1. class Solution { 
  2.     public TreeNode buildTree(int[] preorder, int[] inorder) { 
  3.         return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); 
  4.     } 
  5.  
  6.     public TreeNode helper(int[] preorder, int preLeft, int preRight, 
  7.                            int[] inorder, int inLeft, int inRight) { 
  8.         // 遞歸終止條件 
  9.         if (inLeft > inRight || preLeft > preRight) return null; 
  10.  
  11.         // val 為前序遍歷第一個的值，也即是根節(jié)點的值 
  12.         // idx 為根據根節(jié)點的值來找中序遍歷的下標 
  13.         int idx = inLeft, val = preorder[preLeft]; 
  14.         TreeNode root = new TreeNode(val); 
  15.         for (int i = inLeft; i <= inRight; i++) { 
  16.             if (inorder[i] == val) { 
  17.                 idx = i; 
  18.                 break; 
  19.             } 
  20.         } 
  21.  
  22.         // 根據 idx 來遞歸找左右子樹 
  23.         root.left = helper(preorder, preLeft + 1, preLeft + (idx - inLeft), 
  24.                          inorder, inLeft, idx - 1); 
  25.         root.right = helper(preorder, preLeft + (idx - inLeft) + 1, preRight, 
  26.                          inorder, idx + 1, inRight); 
  27.         return root; 
  28.     } 
  29. } 

Python

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

  1. class Solution: 
  2.     def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: 
  3.         # 第一步: 特殊情況討論: 樹為空. 或者說是遞歸終止條件 
  4.         if not preorder: 
  5.             return None 
  6.  
  7.         # 第二步: 前序遍歷的第一個就是當前的中間節(jié)點. 
  8.         root_val = preorder[0] 
  9.         root = TreeNode(root_val) 
  10.  
  11.         # 第三步: 找切割點. 
  12.         separator_idx = inorder.index(root_val) 
  13.  
  14.         # 第四步: 切割inorder數組. 得到inorder數組的左,右半邊. 
  15.         inorder_left = inorder[:separator_idx] 
  16.         inorder_right = inorder[separator_idx + 1:] 
  17.  
  18.         # 第五步: 切割preorder數組. 得到preorder數組的左,右半邊. 
  19.         # ⭐️ 重點1: 中序數組大小一定跟前序數組大小是相同的. 
  20.         preorder_left = preorder[1:1 + len(inorder_left)] 
  21.         preorder_right = preorder[1 + len(inorder_left):] 
  22.  
  23.         # 第六步: 遞歸 
  24.         root.left = self.buildTree(preorder_left, inorder_left) 
  25.         root.right = self.buildTree(preorder_right, inorder_right) 
  26.  
  27.         return root 

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

  1. class Solution: 
  2.     def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: 
  3.         # 第一步: 特殊情況討論: 樹為空. (遞歸終止條件) 
  4.         if not postorder: 
  5.             return None 
  6.  
  7.         # 第二步: 后序遍歷的最后一個就是當前的中間節(jié)點. 
  8.         root_val = postorder[-1] 
  9.         root = TreeNode(root_val) 
  10.  
  11.         # 第三步: 找切割點. 
  12.         separator_idx = inorder.index(root_val) 
  13.  
  14.         # 第四步: 切割inorder數組. 得到inorder數組的左,右半邊. 
  15.         inorder_left = inorder[:separator_idx] 
  16.         inorder_right = inorder[separator_idx + 1:] 
  17.  
  18.         # 第五步: 切割postorder數組. 得到postorder數組的左,右半邊. 
  19.         # ⭐️ 重點1: 中序數組大小一定跟后序數組大小是相同的. 
  20.         postorder_left = postorder[:len(inorder_left)] 
  21.         postorder_right = postorder[len(inorder_left): len(postorder) - 1] 
  22.  
  23.         # 第六步: 遞歸 
  24.         root.left = self.buildTree(inorder_left, postorder_left) 
  25.         root.right = self.buildTree(inorder_right, postorder_right) 
  26.  
  27.         return root 

 

責任編輯：姜華 來源： 代碼隨想錄
二叉樹數據結構算法
相關推薦

2022-10-26 23:58:02

二叉樹數組算法

2021-04-20 08:37:14

數據結構二叉樹樹

2021-03-22 08:23:29

LeetCode二叉樹節(jié)點

2020-04-27 07:05:58

二叉樹左子樹右子樹

2013-07-15 16:35:55

二叉樹迭代器

2023-05-08 15:57:16

二叉樹數據結構

2024-01-23 12:54:00

C++編程語言代碼

2020-09-23 18:25:40

算法二叉樹多叉樹

2021-09-15 07:56:32

二叉樹層次遍歷

2021-04-28 20:12:27

數據結構創(chuàng)建

2021-01-13 10:03:36

二叉樹層序遍歷層次遍歷

2009-08-11 13:29:57

C#二叉樹遍歷

2021-04-19 07:47:42

數據結構二叉樹Tree

2021-03-17 08:19:22

二叉樹LeetCode樹

2021-09-13 17:58:11

二叉樹層序算法

2021-07-13 11:32:41

二叉樹數據結構算法

2021-09-29 10:19:00

算法平衡二叉樹

2021-09-15 07:40:50

二叉樹數據結構算法

2023-02-01 07:27:46

序列化二叉樹根節(jié)點

2021-05-06 17:46:30

二叉樹數據結構
點贊
收藏

51CTO技術棧公眾號