验证二叉搜索树

难度：中等 Medium (35.96%)

问题描述

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

1. 节点的左子树只包含 小于 当前节点的数。

2. 节点的右子树只包含 大于 当前节点的数。

3. 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

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

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

算法思路

二叉搜索树具备其中序遍历是递增序列，可以先对root节点进行一遍中序遍历，存放到list中，再对list顺序遍历，如果有一对数值为逆序且相等，则说明其不是二叉搜索树。也可以使用一个栈进行中序遍历操作和一个数值记录当前最大值，如果当前最大值小于栈顶，则返回false。

代码实现 Java语言

    /*
 * @lc app=leetcode.cn id=98 lang=java
 *
 * [98] 验证二叉搜索树，方法1
 */

// @lc code=start
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 {
    List<Integer> list = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        inorder(root);
        for (int i = 1; i < list.size(); i++){
            System.out.println(list.get(i - 1) + " " + list.get(i));
            if (list.get(i) <= list.get(i - 1)){
                return false;
            }
        }
        return true;
    }
    void  inorder(TreeNode root1){
        
        if (root1 == null){
            return;
        }
        inorder(root1.left);
        list.add(root1.val);
        inorder(root1.right);
    }


}

// 方法二
class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        long pre = Long.MIN_VALUE;

        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (cur.val <= pre){
                return false;
            }
            pre = cur.val;
            cur = cur.right;
        }

        return true;
    }

}

算法复杂度分析

时间复杂度 O(n) , 对于方法一 n个节点的树，每个节点最大可能被访问两次，为O（2n），复杂度为O(n)数量级,对于方法二,每个节点最大可能被访问1次，为O（n）
空间复杂度O（n），对于方法一，使用了list列表和递归栈，对于方法二，仅使用一个大小为n的栈

执行效率

方法一

方法二

平衡二叉树

难度 Easy (56.93%)

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内

• -104 <= Node.val <= 104

算法思路

通过递归获取左子树高度和右子树高度，如果左子树高度和右子树高度之差大于1，return false，反之，继续分别求左子树和右子树是否是平衡二叉树的与

代码实现 C语言

/**

• Definition for a binary tree node.

• struct TreeNode {

• int val;

• struct TreeNode *left;

• struct TreeNode *right;

• };
  */

int getHeight(struct TreeNode* root){

if (root == NULL)
    return 0;
int left = getHeight(root->left);
int right = getHeight(root->right);
return left > right ? left + 1 : right + 1;

}

bool isBalanced(struct TreeNode* root){

if (root == NULL) 
    return true;
int left = 0; // 左子树的深度
int right = 0; // 右子树的深度
if (root->left != NULL)
    left = getHeight(root->left); // 获取左子树的深度
if (root->right != NULL)
    right = getHeight(root->right); // 获取右子树的深度
if (abs(left - right) > 1) // 如果左右子树的深度差大于1，则不平衡
    return false;
else{
    return isBalanced(root->left) && isBalanced(root->right);
}

}

执行效率