萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣98题-验证二叉搜索树-DFS中序遍历题解

发表于 2021-03-31 | 分类于 力扣刷题 | 0 | 阅读次数 237

题目描述

给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:

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

样例

  1. 样例1:
    输入:
      2
     / \
    1  3
    输出: true

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

题目评估

知识点:DFS、树、递归
难度:中等

题目分析

一个二叉排序树的中序遍历一定是升序的,所以我们直接中序遍历,检验得到的排序是否升序即可,但是我们不用存储这个排序数组,只要记录一个数字,将下轮得到的数字和上个数字进行比较即可。

Java代码题解

递归DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    long beforeVal = Long.MIN_VALUE;  // 定义一个long型记录上一个节点的值

    public boolean isValidBST(TreeNode root) {
        if (root == null) {  // 如果当前节点为null直接返回true
            return true;
        }

        boolean leftFlag = isValidBST(root.left);  // 递归左子树

        if (root.val <= beforeVal) {  // 如果当前节点的值小于上一个中序遍历的值直接返回false
            return false;
        }
        beforeVal = root.val;  // 将本次节点的值记录到beforeVal
        
        boolean rightFlag = isValidBST(root.right);  // 遍历右子树

        return leftFlag && rightFlag;

    }

}
力扣98题

复杂度分析:
中序遍历时间复杂度为O(n)
递归调用使用栈空间,空间复杂度为O(n)

非递归DFS

//import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    long beforeVal = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        
        // 定义一个栈用来存储未中序遍历过的左子树
        Stack<TreeNode> stack = new Stack<TreeNode>();

        long before = Long.MIN_VALUE;  // 定义一个数字用来存储上一个中序遍历的值

        while (root != null || !stack.empty()) {  // 栈不空 树不空 就一直运行
            while (root != null) {  // 把左子树存到栈中
                stack.push(root);
                root = root.left;
            }

            // 遍历到无左子树的节点后弹出无左子树的节点
            root = stack.pop();

            if (root.val <= beforeVal) {  // 把它和中序遍历排序上一个数字比较
                return false;  // 如果小于等于上一个数字直接返回false
            }
            beforeVal = root.val;  // 把本次数字赋值为上一个数字

            root = root.right;  // 同样的操作处理这个节点的右子树
        }
        return true;
    }
}
力扣98题

复杂度分析:
中序遍历一遍顺序遍历,时间复杂度为O(n)
在遍历的过程中使用栈做辅助存储,空间复杂度为O(n)

# 算法 # 程序设计
力扣23题-合并K个升序链表-分治题解分析
MySQL的数据类型
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持