題目描述

根據(jù)前序遍歷和中序遍歷樹構造二叉樹.

樣例

給出中序遍歷：[1,2,3]和前序遍歷：[2,1,3]. 返回如下的樹:

  2
 / \
1   3

思路

先序遍歷的第一個數(shù)為根值，在中序遍歷的數(shù)組中找到該值，并則在該值左邊為其左子樹，右邊為其右子樹。

實現(xiàn)

/**
 * @param preorder : 樹的先序遍歷列表
 * @param inorder :  樹的中序遍歷列表
 * @return : Root of a tree
 */

/**
 
 使用先序遍歷和中序遍歷構造樹的遞歸方法

 @param preorder 樹的先序遍歷列表
 @param inorder 樹的中序遍歷列表
 @param preStart 樹的先序遍歷列表起始位置
 @param preEnd 樹的先序遍歷列表結束位置
 @param inStart 樹的中序遍歷列表起始位置
 @param inEnd 樹的中序遍歷列表結束位置
 @return 根節(jié)點
 */
TreeNode * buildTreeCore(vector<int> &preorder, vector<int> &inorder,int preStart, int preEnd, int inStart, int inEnd){
    
    //構造根節(jié)點
    int rootVal = preorder[preStart];
    TreeNode *root = new TreeNode(rootVal);
    if (preStart == preEnd) {
        return root;
    }
    
    //找到在中序遍歷中的根節(jié)點
    int indexOfRoot = inStart;
    while (rootVal != inorder[indexOfRoot] && indexOfRoot < inEnd) {
        indexOfRoot++;
    }
    
    //判斷是否存在左子樹，若有則遞歸構造左子樹
    if (indexOfRoot > inStart) {
        root -> left = buildTreeCore(preorder, inorder, preStart + 1, preStart + (indexOfRoot - inStart), inStart, indexOfRoot - 1);
    }
    
    //判斷是否存在右子樹，若有則遞歸構造右子樹
    if (indexOfRoot < inEnd) {
        root -> right = buildTreeCore(preorder, inorder, preStart + (indexOfRoot - inStart) + 1, preEnd, indexOfRoot+1, inEnd);
    }
    
    return root;
}

/**
 使用先序遍歷和中序遍歷構造樹

 @param preorder 樹的先序遍歷列表
 @param inorder 樹的中序遍歷列表
 @return 根節(jié)點
 */
TreeNode* buildTree(vector<int> &preorder, vector<int> &inorder) {
    //參數(shù)檢查
    if (preorder.size() <= 0 ||
        inorder.size() <= 0  ||
        preorder.size() != inorder.size()) {
        return NULL;
    }
    
    TreeNode *root = buildTreeCore(preorder, inorder, 0, (int)preorder.size()-1, 0, (int)inorder.size() - 1);
    return root;
}