一级域名网站如何申请,任丘网站建设价格,如何替换网站的图片,百度输入法下载文章目录 一、题目二、C# 题解 一、题目 实现一个函数#xff0c;检查一棵二叉树是否为二叉搜索树。 点击此处跳转题目。
示例 1: 输入: 2/ \
1 3输出: true 示例 2: 输入: 5/ \1 4/ \
3 6输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 #xff… 文章目录 一、题目二、C# 题解 一、题目 实现一个函数检查一棵二叉树是否为二叉搜索树。 点击此处跳转题目。
示例 1: 输入: 2/ \
1 3输出: true 示例 2: 输入: 5/ \1 4/ \
3 6输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 但是其右子节点值为 4 。 二、C# 题解 检查是否为二叉搜索树即看该树的中序遍历是否已排序。一种方法是中序遍历后将每个值存储至数组中再判断数组内元素是否已排序。但该方法对每个元素访问了两次中序遍历读取依次数组中读取一次因此可以进行优化。中序遍历从左至右顺序访问结点可以直接对值进行比较只需额外使用一个结点记录上次访问的内容即可具体实现如下
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int x) { val x; }* }*/
public class Solution {public bool IsValidBST(TreeNode root) {TreeNode tn null;return Partition(root, ref tn);}// 递归中序遍历进行检查public bool Partition(TreeNode node, ref TreeNode last) {if (node null) return true; // 递归出口if (!Partition(node.left, ref last)) return false; // 左子树检查if (last ! null node.val last.val) return false; // 结点判断last node; // 更新上一个结点return Partition(node.right, ref last); // 右子树检查}
}这里进行了剪枝处理即当左子树或者该结点不满足条件时直接返回 false避免了右子树的访问。
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。
