題目

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

分析

前面講過根據前序和中序構建二叉樹：博客鏈接
這道題是告訴我們一顆二叉樹的后序和中序，讓我們根據后序和中序構造出整顆二叉樹。
拿到這道題，我們首先要知道中序的后序又怎樣的性質：

• 中序：【左 根 右】
• 后序：【左 右 根】

根據以上的性質，我們可以得到以下的結論：

• 后序遍歷的最后一個元素一定為數的根節點node的值。
• 因為題目告訴了我們無重復元素，所以在中序遍歷中找到根節點 node 的索引，可以將 中序遍歷的數組 劃分為 【左子樹 | 根節點 | 右子樹】 的形式。
• 在中序遍歷數組中我們可以知道以 node 為根節點，左右子樹的節點個數，利用這點可以將 后序遍歷數組 劃分為 【左子樹 | 右子樹 根節點 】。
• 通過上面我們可以知道整顆樹的樹根，左子樹，右子樹。下面需要分別構建左子樹、右子樹，還是按照上面的邏輯。

接下來的問題就是需要知道構建左子樹和右子樹的時候的前序序列和中序序列。

• 根節點的值為 postorder[postorder.length-1]，然后在中序序列中找到這個節點下標為 rootInorderIndex
• 構建左子樹：

左子樹的 inorder :[0,rootInorderIndex)
左子樹的 postorder :[0,rootInorderIndex)

• 構建右子樹：

右子樹的 inorder :[rootInorderIndex+1,inorder.length)
右子樹的 postorder :[rootInorderIndex,postorder.length - 1)

代碼

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(inorder.length == 0) return null;int rootValue = postorder[postorder.length - 1];TreeNode root = new TreeNode(rootValue);int rootInorderIndex = -1;for(int i = 0;i < inorder.length;i ++) {if(inorder[i] == rootValue) {rootInorderIndex = i;break;}}root.left = buildTree(Arrays.copyOfRange(inorder,0,rootInorderIndex),Arrays.copyOfRange(postorder,0,rootInorderIndex));root.right = buildTree(Arrays.copyOfRange(inorder,rootInorderIndex+1,inorder.length),Arrays.copyOfRange(postorder,rootInorderIndex,postorder.length - 1));return root;}
}