Binary tree related algorithms summary

1970 단어 두 갈래 나무

validate a binary tree is BST


사고방식: bst의 중차 역행 서열은 엄격하게 점차적으로 증가한다.1. 빈 트리는 BST 2.왼쪽 나무는 BST & 오른쪽 나무는 BST 3.왼쪽 트리 & 뿌리 & 오른쪽 트리는 BST를 구성할 수 있습니다. sample code
    /*  BST 
     *  ： ， 
     *  O(n), 。
     *  ： bst 
     */
    bool is_bst_by_in(node *root, int& preval)
    {
        if (!root)  return true;  /*   */     
        if (is_bst_by_in(root->l, preval))
        {
            if (root->dat > preval) /*   */
            {
                preval = root->dat;
                return is_bst_by_in(root->r, preval);
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }

bool isBst(node *root)
{
    int pre = INT_MIN;
    return is_bst(root, pre);
}

determine whether a binary search tree pre-order traversal sequence is valid


for a pre-ordered binary search tree traversal sequence, to determine whether it is valid is somewhat difficult in a linear time complexity. you need to check each sub trees in root left right order. A stack can help solve the problem.
두 갈래 찾기 트리 (둘)
leetcode 알고리즘 문제 687(간단 174) 최장 동치 경로

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage