leetcode 98. 인증 두 갈래 검색 트리

1215 단어 leetcode
두 갈래 나무를 정해 효과적인 두 갈래 검색 나무인지 아닌지를 판단한다.
두 갈래 검색 트리에는 다음과 같은 정의가 있습니다.
  • 왼쪽 트리는 현재 노드보다 작은 수만 포함합니다.
  • 오른쪽 트리는 현재 노드보다 큰 수만 포함합니다.
  • 모든 하위 트리 자체도 두 갈래 검색 트리여야 한다.

  • 예 1:
        2
       / \
      1   3
    

    두 갈래 나무[2,1,3],true로 돌아갑니다.
    예 2:
        1
       / \
      2   3
    

    두 갈래 나무[1,2,3],false로 돌아갑니다.
    나 좀 어리석었어.중서 역행
    /**
     * 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:
         bool isValidBST(TreeNode* root) {
            if (root) {
                long long f = -0x3f3f3f3f3f3f;
                return dfs(root, f);
            }
            else
                return true;
        }
        
        bool dfs(TreeNode* root, long long& f_val) {
            bool res = true;
            if (root) {
                res &= dfs(root->left, f_val) && (root->val > f_val);
                if (!res)
                    return false;
                f_val = root->val;
                res &= dfs(root->right, f_val);
            }
            return res;
        }
    };

    좋은 웹페이지 즐겨찾기