「力扣」第 98 题:验证二叉搜索树(中等)


「力扣」第 98 题:验证二叉搜索树(中等)

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

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

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ,但是其右子节点值为 4 。

分析:二分搜索树定义 3 条,根据定义判断其实是最简单的,在技巧上就是要分一下,是左子树还是右子树。

方法一: 中序遍历判断有序性

说明:这个方法是最容易想到的,直接利用了「二叉搜索树」中序遍历的性质。

Java 代码:

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        List<Integer> res = new ArrayList<>();
        inOrder(root, res);

        int len = res.size();
        for (int i = 0; i < len - 1; i++) {
            if (res.get(i) >= res.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    private void inOrder(TreeNode treeNode, List<Integer> res) {
        if (treeNode == null) {
            return;
        }
        inOrder(treeNode.left, res);
        res.add(treeNode.val);
        inOrder(treeNode.right, res);
    }
}

方法二:中序遍历

分析:这个方法知道就可以了。

Java 代码:

public class Solution2 {

    private long last = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (isValidBST(root.left)) {
            if (last < root.val) {
                last = root.val;
                return isValidBST(root.right);
            }
        }
        return false;
    }
}

方法三:深度优先遍历

即「依据定义」,前序遍历。

Java 代码:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}


public class Solution {

    public boolean isValidBST(TreeNode root) {
        // 依据定义
        if (root == null) {
            return true;
        }
        return dfs(root.left, root.val, true) &&
                dfs(root.right, root.val, false) &&
                isValidBST(root.left) && isValidBST(root.right);
    }

    /**
     * @param node   当前结点
     * @param val    父亲结点的值
     * @param ifLeft 表示传入的结点是否是左结点
     * @return
     */
    private boolean dfs(TreeNode node, int val, boolean ifLeft) {
        if (node == null) {
            return true;
        }
        if (ifLeft) {
            if (node.val >= val) {
                return false;
            }
            return dfs(node.left, val, true) && dfs(node.right, val, true);
        } else {
            if (node.val <= val) {
                return false;
            }
            return dfs(node.left, val, false) && dfs(node.right, val, false);
        }
    }
}
  • 另一种写法

Java 代码:

public class Solution {

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return dfs(root, null, null);
    }

    private boolean dfs(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }
        if (min != null && node.val <= min) {
            return false;
        }
        if (max != null && node.val >= max) {
            return false;
        }
        return dfs(node.left, min, node.val) && dfs(node.right, node.val, max);
    }
}

(本节完)


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 387 题:字符串中的第一个唯一字符 「力扣」第 387 题:字符串中的第一个唯一字符
「力扣」第 387 题:字符串中的第一个唯一字符 链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string 给定一个字符串,找到它的第一个不重复的字符,
下一篇 
「力扣」第 53 题:最大子序和(中等) 「力扣」第 53 题:最大子序和(中等)
「力扣」第 53 题:最大子序和(中等) 提示:经典的「动态规划」问题,一定要掌握。 动态规划告诉我们可以不用直接去解决题目,而是去发现这个问题最开始的样子,通过「状态」转移,每一步参考了之前计算的结果,得到最终的答案。 链接 题解链接
  目录