1008.Construct Binary Search Tree from Preorder Traversal

1008.Construct Binary Search Tree from Preorder Traversal

难度:Medium

返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）

示例：

输入：[8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]

1266.png

提示：

1 <= preorder.length <= 100 先序 preorder 中的值是不同的。

先序遍历，先遍历根节点和左孩子，然后到底之后再遍历右边的。不断回溯。 所以当下一个节点比当前节点小时，直接添加左孩子即可。 当其比较大时，不断回溯比较，找到大于该节点的根节点，然后从其左子树开始比较，如果不存在右孩子，则将其添加为右孩子。如果有，则比较其右孩子的右孩子(左边之前已经遍历过了)，不断循环，最后将其添加为右孩子即可。 代码实现如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root = new TreeNode(preorder[0]);

        stack<TreeNode*> s;
        s.push(root);
        for(int i=1;i<preorder.size();i++)
        {
            TreeNode* cur = s.top();
            if(preorder[i] <cur->val ) 
            {
                cur->left = new TreeNode(preorder[i]);
               s.push(cur->left);


            }
            else
            {
                while( s.size()>1 &&  cur->val < preorder[i])
                {
                s.pop();
                cur = s.top();
                }
                if( cur->val < preorder[i]){
                while(cur->right)
                {
                    s.push(cur->right);
                    cur=cur->right;
                }
                 cur->right = new TreeNode(preorder[i]);
                }
                else{
                    s.push(cur->left);
                    cur=cur->left;
                while(cur->right )
                {
                    s.push(cur->right);
                    cur=cur->right;
                }
                // cout<<cur->val<<endl;
       

                cur->right = new TreeNode(preorder[i]);

                }
                s.push(cur->right);
                  
            }
            
            
        }
        return root;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了96.01%的用户 内存消耗 :9 MB, 在所有 C++ 提交中击败了87.58%的用户