leetcode98.二叉搜索树

Posted on | In |
Words count in article: 403 | Reading time ≈ 2

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例：

1
2
输入：root = [2,1,3]
输出：true

分析：

1
只需要保证左子树的最大值小于root,右子树的最小值大于root

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        int max_value, min_value;

        return dfs(root, max_value, min_value);
    }
	
    // 借助引用实现自下而上传递
    bool dfs(TreeNode* root, int& max_value, int& min_value) {
        min_value = max_value = root->val;
        if (root->left) {
            int now_max, now_min;
            if (!dfs(root->left, now_max, now_min))
                return false;
            if (now_max >= root->val)
                return false;
            max_value = max(max_value, now_max);
            min_value = min(min_value, now_min);
        }

        if (root->right) {
            int now_max, now_min;
            if (!dfs(root->right, now_max, now_min))
                return false;
            if (now_min <= root->val)
                return false;
            max_value = max(max_value, now_max);
            min_value = min(min_value, now_min);
        }

        return true;
    }
};

  • Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func dfs(root *TreeNode, min_value, max_value int) bool {
    if root == nil {
        return true
    }

    if (root.Val <= min_value || max_value <= root.Val) {
        return false;
    }

    return dfs(root.Left, min_value, root.Val) && dfs(root.Right, root.Val, max_value)
}

func isValidBST(root *TreeNode) bool {
    return dfs(root, math.MinInt64, math.MaxInt64)
}

[原题链接](98. 验证二叉搜索树 - 力扣（Leetcode）)

0%