把題目的要求細化，搞清楚根節點應該做什么，然后剩下的事情拋給前/中/后序的遍歷框架就行了，我們千萬不要跳進遞歸的細節里，你的腦袋才能壓幾個棧呀。

654.最大二叉樹

分析：
1.根節點要做什么？？
把自己構建出來。
2.具體做什么？？
遍歷數組把找到最大值 maxVal，把根節點 root 做出來，然后對 maxVal 左邊的數組和右邊的數組進行遞歸調用，作為 root 的左右子樹。
解題思路：

TreeNode constructMaximumBinaryTree([3,2,1,6,0,5]) {    // 找到數組中的最大值    TreeNode root = new TreeNode(6);    // 遞歸調用構造左右子樹    root.left = constructMaximumBinaryTree([3,2,1]);    root.right = constructMaximumBinaryTree([0,5]);    return root;}

解答：

/* 主函數 */TreeNode constructMaximumBinaryTree(int[] nums) {    return build(nums, 0, nums.length - 1);}/* 將 nums[lo..hi] 構造成符合條件的樹，返回根節點 */TreeNode build(int[] nums, int lo, int hi) {    // base case    if (lo > hi) {        return null;    }    // 找到數組中的最大值和對應的索引    int index = -1, maxVal = Integer.MIN_VALUE;    for (int i = lo; i <= hi; i++) {        if (maxVal < nums[i]) {            index = i;            maxVal = nums[i];        }    }    TreeNode root = new TreeNode(maxVal);    // 遞歸調用構造左右子樹    root.left = build(nums, lo, index - 1);    root.right = build(nums, index + 1, hi);        return root;}

105.根據前序和中序序列構造二叉樹

??重點題型標注！

分析：
想辦法確定根節點的值，把根節點做出來，然后遞歸構造左右子樹即可。
如何找到根節點？？

前序遍歷的第一個值preorder[0]就是根節點的值，關鍵在于如何通過根節點的值，將preorder和postorder數組劃分成兩半，構造根節點的左右子樹？

根據思路寫出對應的代碼為：

/* 主函數 */TreeNode buildTree(int[] preorder, int[] inorder) {    return build(preorder, 0, preorder.length - 1,                 inorder, 0, inorder.length - 1);}/*    若前序遍歷數組為 preorder[preStart..preEnd]，   后續遍歷數組為 postorder[postStart..postEnd]，   構造二叉樹，返回該二叉樹的根節點 */TreeNode build(int[] preorder, int preStart, int preEnd,                int[] inorder, int inStart, int inEnd) {    // root 節點對應的值就是前序遍歷數組的第一個元素    int rootVal = preorder[preStart];    // rootVal 在中序遍歷數組中的索引    int index = 0;    for (int i = inStart; i <= inEnd; i++) {        if (inorder[i] == rootVal) {            index = i;            break;        }    }    TreeNode root = new TreeNode(rootVal);    // 遞歸構造左右子樹    root.left = build(preorder, ?, ?,                      inorder, ?, ?);    root.right = build(preorder, ?, ?,                       inorder, ?, ?);    return root;}

得到構造左右子樹的代碼：

解答：

/** * 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 {TreeNode buildTree(int[] preorder, int[] inorder) {    return build(preorder, 0, preorder.length - 1,                 inorder, 0, inorder.length - 1);}/*    若前序遍歷數組為 preorder[preStart..preEnd]，   后續遍歷數組為 postorder[postStart..postEnd]，   構造二叉樹，返回該二叉樹的根節點 */ TreeNode build(int[] preorder, int preStart, int preEnd,                int[] inorder, int inStart, int inEnd) {    if (preStart > preEnd) {        return null;    }    // root 節點對應的值就是前序遍歷數組的第一個元素    int rootVal = preorder[preStart];    // rootVal 在中序遍歷數組中的索引    int index = 0;    for (int i = inStart; i <= inEnd; i++) {        if (inorder[i] == rootVal) {            index = i;            break;        }    }    int leftSize = index - inStart;    // 先構造出當前根節點    TreeNode root = new TreeNode(rootVal);    // 遞歸構造左右子樹    root.left = build(preorder, preStart + 1, preStart + leftSize,                      inorder, inStart, index - 1);    root.right = build(preorder, preStart + leftSize + 1, preEnd,                       inorder, index + 1, inEnd);    return root;}}

106.根據中序和后續遍歷構造二叉樹

分析：
有了上一題的基礎，發現只要畫圖發現左右子樹的起止點就可以了。



代碼實現：

class Solution {    public TreeNode buildTree(int[] inorder, int[] postorder) {        return build(inorder,0,inorder.length-1,                postorder,0,postorder.length-1);    }    /**構建二叉樹 */    TreeNode build(int[] inorder, int inStart, int inEnd,               int[] postorder, int postStart, int postEnd) {    if (inStart > inEnd) {        return null;    }    // root 節點對應的值就是后序遍歷數組的最后一個元素    int rootVal = postorder[postEnd];    // rootVal 在中序遍歷數組中的索引    int index = 0;    for (int i = inStart; i <= inEnd; i++) {        if (inorder[i] == rootVal) {            index = i;            break;        }    }    // 左子樹的節點個數    int leftSize = index - inStart;    TreeNode root = new TreeNode(rootVal);    // 遞歸構造左右子樹    root.left = build(inorder, inStart, index - 1,                        postorder, postStart, postStart + leftSize - 1);    root.right = build(inorder, index + 1, inEnd,                        postorder, postStart + leftSize, postEnd - 1);    return root;}}