目錄

一、二叉樹理論知識

二、構造二叉樹思路

2.1 構造二叉樹流程（給定中序+后序

2.2 整體步驟

2.3 遞歸思路

2.4?給定前序和后序

三、相關算法題目

四、易錯點

---

一、二叉樹理論知識

詳見：代碼隨想錄刷題day34|（二叉樹篇）二叉樹的遞歸遍歷-CSDN博客

二、構造二叉樹思路

2.1 構造二叉樹流程（給定中序+后序

給定中序和后序的節點值構造唯一二叉樹：

中序：左中右：9 3 15 20 7

后序：左右中：9 15 7 20 3

由后序可知：最后一個結點 3 一定為根節點? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?9 15 7 20 3

由中序可知：左子樹為 9 右子樹為 15 20 7? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??9 3 15 20 7

由后序可知：左子樹的根節點為 9 （也只有唯一一個結點?9?）右子樹的根節點為 20?

由中序可知：右子樹的左節點為 15? ?右節點為 7

2.2 整體步驟

1.如果后序數組為空，則說明遍歷結束；

2.后序數組最后一個元素為(根)結點元素；

3.在中序數組中尋找對應結點元素，作為切割點，分割左右子樹；

4.切割中序數組，切成左右區間；

5.切割后序數組：根據中序數組中的左右區間，再去切割后序數組中的左右區間；

6.然后遞歸處理切割后的左區間和右區間；

2.3 遞歸思路

1.遞歸函數返回值和參數

返回構造好的根節點，參數：中序數組和后序數組；

2.終止條件

后序數組為空，返回為空，假設后序數組長度＝中序數組長度，不考慮其他異常情況；

3.單層遞歸邏輯

處理特殊情況：如果后序數組長度為1，則說明這棵樹只有一個結點，即為根節點又為葉子節點；

首先獲取后序數組中最后一個結點的值val；

遍歷中序數組，找到val所在的下標位置index；

根據index切割中序數組，得到左中序數組、右中序數組；

根據左中序數組的大小和右中序數組的大小來切割后序數組，得到左后序數組、右后序數組；

根據左中序和左后序遞歸處理左子樹，右中序和右后序遞歸處理結點的右子樹；

最后返回根節點；

一定先切中序，分開左右，再去切后序，否則后序無法分開左右；

2.4?給定前序和后序

不可以

因為只能找出根節點，但是分不開左右區間，構造二叉樹一定要有中序遍歷的數組；

三、相關算法題目

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

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {return backtracking(inorder,postorder);}private TreeNode backtracking(int[] inorder, int[] postorder){if(postorder.length == 0 || inorder.length == 0){return null;}TreeNode root = new TreeNode();root.val = postorder[postorder.length - 1];if(postorder.length == 1){return root;}int index = 0;for(int i = 0;i < inorder.length;i++){if(inorder[i] == postorder[postorder.length - 1]){index = i;break;}}//切割中序數組 得到左中序數組int[] leftInorder = Arrays.copyOfRange(inorder,0,index);//得到右中序數組int[] rightInorder = Arrays.copyOfRange(inorder,index + 1,inorder.length);//切割后序數組 得到左后序數組int[] leftPostorder = Arrays.copyOfRange(postorder,0,leftInorder.length);//得到右后序數組int[] rightPostorder = Arrays.copyOfRange(postorder,leftInorder.length,postorder.length - 1);//遞歸處理左子樹 根據左中序和左后序root.left = backtracking(leftInorder,leftPostorder);//遞歸處理右子樹 根據右中序和右后序root.right = backtracking(rightInorder,rightPostorder);return root;}
}

四、易錯點

1.判斷后序數組和中序數組長度是否為0，要放在遞歸函數中，否則當左子樹為空時，遞歸到下一層，即根結點的左子樹時，后序數組已為空，長度為0，但此時不進行長度為0的校驗，那么通過 后序數組的長度-1 來獲取根節點的值 就會報錯：

ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 0

2.獲取左中序、右中序、左后序、右后序數組時，起始索引和終止索引要注意，起始索引包括，中止索引不包括，右后序中，終止索引要考慮去掉后序數組中的最后一個結點（根節點），即 postorder.length - 1；

3.優化建議：

• 可以用?HashMap?預處理?inorder?的值到索引的映射，避免每次遞歸都遍歷查找?index。

• 可以用索引范圍代替數組拷貝，減少空間開銷（傳遞?inorder?和?postorder?的起始和結束索引，而不是拷貝數組）。

4.切數組的時候 注意區間的定義，左閉右開，左閉右閉

一定打日志 來找問題？ debug？就是把每一步劃分的數組打印出來看 printf

待續。。。。