构造二叉树——105. 从前序与中序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //root调用函数
    TreeNode* buildTree(vector<int>& preOrder, vector<int>& inOrder) {
        return buildNode(preOrder, 0, preOrder.size() - 1,
                        inOrder, 0, inOrder.size() - 1);
    }

    //--
    TreeNode* buildNode(vector<int>& preOrder,int preSta,int preEnd,
                        vector<int>& inOrder,int inSta,int inEnd){
        if(preSta > preEnd || inSta > inEnd){//超出边界，返回null
            return nullptr;
        }
        
        //--rootVal：每一轮函数中，构造的树的根节点，
        //--由 前序遍历的第一个节点得到，（前序遍历的第一个节点必定为根节点）
        int rootVal = preOrder[ preSta ];
        TreeNode *root = new TreeNode( rootVal );

        //--rootIndex_inOrder：寻找根节点在中序遍历列表的位置，
        //--用于 分隔 中序遍历列表的 左右两端
        int rootIndex_inOrder = 0;
        for(int i = inSta; i <= inEnd; i++){
            if(inOrder[ i ] == rootVal){
                rootIndex_inOrder = i;
                break;
            }
        }

        //--标记 前序遍历的左子树 在前序的列表的位置的偏移，详见图
        int in_LeftSide_Size = rootIndex_inOrder - inSta;
        
        //--分段方法 详见图
        root->left = buildNode(preOrder, preSta + 1, preSta + in_LeftSide_Size ,
                                inOrder, inSta, rootIndex_inOrder - 1);
        root->right = buildNode(preOrder, preSta + in_LeftSide_Size + 1 ,preEnd,
                                inOrder,rootIndex_inOrder + 1, inEnd);
        return root;
    }
};