인증 두 갈래 찾기 트리

1672 단어

두 갈래 찾기 트리


두 갈래 트리를 지정해서 합법적인 두 갈래 찾기 트리 (BST) 인지 아닌지 판단하기
BST 정의:
노드의 왼쪽 트리의 값은 노드의 값보다 엄격하게 작아야 한다.노드의 오른쪽 하위 트리의 값은 노드의 값보다 엄격해야 한다.좌우 나무도 반드시 두 갈래로 나무를 찾아야 한다.
두 갈래 찾기 트리의 중서가 질서정연하기 때문이다.따라서 두 갈래로 트리를 찾는지 확인하고 이 두 갈래 트리를 중순으로 훑어보십시오. 만약에 이전 결점의 값이 현재 결점의 값보다 크면 이것은 두 갈래 트리가 아니라는 것을 증명합니다.

코드 구현

bool isValidBST(TreeNode *root) {
        // write your code here
        if(root == NULL)
            return true;
        stack<TreeNode*> stk;
        TreeNode *pre = NULL;

        while(root || !stk.empty())
        {
            if(root)
            {
                stk.push(root);
                root = root->left;
            }

            else
            {
                root = stk.top();
                stk.pop();
                if(pre && (root->val <= pre->val))
                    return false;
                pre = root;
                root = root->right;
            }
        }

        return true;
    }

(95) Validate Binary Search Tree http://www.lintcode.com/zh-cn/problem/validate-binary-search-tree/

좋은 웹페이지 즐겨찾기