[leetcode] 255. Verify Preorder Sequence in Binary Search Tree解題レポート

1375 ワード
LeetCode tree binary
タイトルリンク:https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up: Could you do it using only constant space complexity?
考え方:現在の値の範囲を維持し、最初の最小最大はルートノードであり、左サブツリーの最小値が左端のノードを維持します.最初の増加ノードを見つけることで、前のノードが左サブツリーの最小値であり、つまりルートノードより小さいすべてのノードがそのノードより大きくなければなりません.
そして右サブツリーを巡ると、最大値と最小値を更新し続けます.現在のノードが最大値より大きい場合は、ルートノードの右端に移動したことを示します.最小値は最大値に更新され、最大値は現在のノードに更新されます.この場合、ノードの右サブツリーに遍歴しているため、この右サブツリーの最小値はルートノードです.
コードは次のとおりです.
class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        if(preorder.size() ==0) return true;
        int Min = preorder[0], Max = Min;
        for(int i = 1; i< preorder.size(); i++)
        {
            if(preorder[i] > preorder[i-1]) break;
            Min = min(Min, preorder[i]);
        }
        for(int i = 0; i< preorder.size(); i++)
        {
            if(preorder[i] < Min) return false;
            if(preorder[i] > Max)
            {
                Min = Max;
                Max = preorder[i]; 
            }
        }
        return true;
    }
};
参照:https://leetcode.com/discuss/89904/52ms-c-o-1-space-o-n-time-commented-code
《leetCode》:Counting Bits
[leetcode] 42. Trapping Rain Water解題レポート