Swift 验证二叉搜索树- LeetCode

LeetCode

题目： 验证二叉搜索树

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

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

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

示例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 {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        guard root != nil else { return true }
        var stack = [TreeNode](), node = root, pre: TreeNode? = nil
        while node != nil || !stack.isEmpty {
            while node != nil {
                stack.append(node!)
                node = node!.left
            }
            node = stack.removeLast()
            if pre != nil && pre!.val >= node!.val {
                return false;
            }
            pre = node
            node = node!.right
        }
        return true
    }
}

方案二：

• 二叉搜索树的左节点一定小于根节点
• 二叉搜索树的右节点一定大于根节点

代码二：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
 
class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        return isValidBSTUtil(root, Int.min, Int.max);
    }
    
    func isValidBSTUtil(_ node: TreeNode?,_ min: Int,_ max: Int) -> Bool {
        guard let node = node else {
            return true
        }
        //左节点需要小于根节点值，右节点需要大于根节点
        guard node.val > min && node.val < max else {
            return false
        }
        return isValidBSTUtil(node.left, min, node.val) && isValidBSTUtil(node.right, node.val, max)
    }
}

对isValidBSTUtil(node.left, min, node.val) && isValidBSTUtil(node.right, node.val, max)
取一个切片：
isValidBSTUtil(node.left, min, node.val)
此时，

• 函数内的 node.val 就是 root.left.val
• 函数内的 min 就是 min
• 函数内的 max 就是 root.val

node.val < max  ->  root.left.val < root.val
node.val > min  ->  root.left.val > min

取另一个一个切片：
isValidBSTUtil(node.right, node.val, max)
此时，

• 函数内的 node.val 就是 root.right.val
• 函数内的 min 就是 root.val
• 函数内的 max 就是 max

node.val < max  ->  root.right.val < max
node.val > min  ->  root.right.val > root.val 

换种写法可能更好理解

//左节点需要小于根节点值，右节点需要大于根节点
 guard node.val > min && node.val < max else {
   return false
 }

/*-------------to---------------->>>>/*

if let min = min, node.val <= min {
  return false
}

if let max = max, node.val >= max {
  return false
}

用Swift开始学习算法中，在LeetCode中开始做初级算法这一章节，将做的题目在此做个笔记，希望有更好方法同学们cue我哦。