首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
拉勾
V2EX  ›  C/C++/Obj-C

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

  •  
  •   Acceml · 32 天前 · 436 次点击
    这是一个创建于 32 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

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

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

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

    示例 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
        1
    ahonn   32 天前 via iPhone
    递归就完了
        2
    aijam   32 天前 via iPhone
    简单递归题需要什么中序
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   826 人在线   最高记录 4385   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 15ms · UTC 22:53 · PVG 06:53 · LAX 15:53 · JFK 18:53
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1