V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  C

[Leetcode] 98. 验证二叉搜索树

  •  
  •   Acceml · 2019-02-19 09:43:31 +08:00 · 1961 次点击
    这是一个创建于 1864 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

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

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

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

    示例 1:

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

    示例 2:

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

    题解

    这道题目主要是利用二叉搜索树的一个性质: 二叉搜索树的中序遍历结果是一个升序的序列。 那么问题转变成:中序遍历 + 验证是不是升序.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        private List<Integer> inPrint(TreeNode root, List<Integer> res) {
            if (root != null) {
                inPrint(root.left, res);
                res.add(root.val);
                inPrint(root.right, res);
            }
            return res;
        }
        
        public boolean isValidBST(TreeNode root) {
            List<Integer> res = inPrint(root, new LinkedList<>());
            if (res.size() == 1) {
                return true;
            }
            for (int i = 1; i < res.size(); i++) {
                if (res.get(i) <= res.get(i - 1)) {
                    return false;
                }
            }
            return true;
        }
    }
    

    Leetcode 名企之路

    2 条回复    2019-02-19 10:05:31 +08:00
    ahonn
        1
    ahonn  
       2019-02-19 10:03:02 +08:00 via iPhone
    递归就完了
    aijam
        2
    aijam  
       2019-02-19 10:05:31 +08:00 via iPhone
    简单递归题需要什么中序
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1388 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 17:31 · PVG 01:31 · LAX 10:31 · JFK 13:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.