leetcode 98. 驗證二叉搜索樹
題目
給你一個二叉樹的根節點 root ,判斷其是否是一個有效的二叉搜索樹。
有效 二叉搜索樹定義如下:
節點的左子樹只包含 小于 當前節點的數。
節點的右子樹只包含 大于 當前節點的數。
所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1:
輸入:root = [2,1,3]
輸出:true
示例 2:
輸入:root = [5,1,4,null,null,3,6]
輸出:false
解釋:根節點的值是 5 ,但是右子節點的值是 4 。
提示:
樹中節點數目范圍在[1, 104] 內
? 2 31 -2^{31} ?231 <= Node.val <= 2 31 ? 1 2^{31} - 1 231?1
思路
其實一開始思路是正常往左右分別遍歷并且判斷當前根節點和左右子樹的大小關系,但是WA了
class Solution {public boolean isValidBST(TreeNode root) {if (root.left == null && root.right == null) {return true;}else if (root.left == null) {return root.val < root.right.val && isValidBST(root.right);}else if (root.right == null) {return root.val > root.left.val && isValidBST(root.left);}else {return root.val > root.left.val && root.val < root.right.val && isValidBST(root.left) && isValidBST(root.right);}}
}
因為上面這個沒考慮到情況
所以其實應該明白中序遍歷是一個左中右的順序,對應到二叉搜索樹,自然就是一個升序序列了,所以寫了這個
class Solution {Deque<Integer> queue = new ArrayDeque<Integer>();public boolean isValidBST(TreeNode root) {dfs(root);int v = queue.pollFirst();System.out.println(v);while (! queue.isEmpty()) {int f = queue.pollFirst();if (v >= f) {return false;}v = f;}return true;}public void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);queue.offerLast(root.val);dfs(root.right);}
}
但是這個隊列的操作會拖慢運行時間,于是修改后如下
代碼
class Solution {TreeNode pre;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}boolean left = isValidBST(root.left);if (pre != null && pre.val >= root.val) {return false;}pre = root;boolean right = isValidBST(root.right);return left && right;}
}