【問題描述】[第98題][驗證二叉搜索樹][中等]

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。假設一個二叉搜索樹具有如下特征：節點的左子樹只包含小于當前節點的數。 節點的右子樹只包含大于當前節點的數。 所有左子樹和右子樹自身必須也是二叉搜索樹。

【解答思路】

1.中序遍歷

中序遍歷是二叉樹的一種遍歷方式，它先遍歷左子樹，再遍歷根節點，最后遍歷右子樹。而我們二叉搜索樹保證了左子樹的節點的值均小于根節點的值，根節點的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。

時間復雜度：O(N) 空間復雜度：O(N)
1.1 遞歸

class Solution {long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 訪問左子樹if (!isValidBST(root.left)) {return false;}// 訪問當前節點：如果當前節點小于等于中序遍歷的前一個節點，說明不滿足BST，返回 false；否則繼續遍歷。if (root.val <= pre) {return false;}pre = root.val;// 訪問右子樹return isValidBST(root.right);} }

1.2 棧

class Solution {public boolean isValidBST(TreeNode root) {Stack<TreeNode> stack = new Stack();double inorder = - Double.MAX_VALUE;while (!stack.isEmpty() || root != null) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();// 如果中序遍歷得到的節點的值小于等于前一個 inorder，說明不是二叉搜索樹if (root.val <= inorder)return false;inorder = root.val;root = root.right;}return true;} }

2. 遞歸

時間復雜度：O(N) 空間復雜度：O(N)

public boolean helper(TreeNode node, Integer lower, Integer upper) {if (node == null) return true;int val = node.val;if (lower != null && val <= lower) return false;if (upper != null && val >= upper) return false;if (! helper(node.right, val, upper)) return false;if (! helper(node.left, lower, val)) return false;return true;}public boolean isValidBST(TreeNode root) {return helper(root, null, null);}

【總結】

1. 二叉樹遍歷

• 前序遍歷 先輸出當前結點的數據，再依次遍歷輸出左結點和右結點
• 中序遍歷 先遍歷輸出左結點，再輸出當前結點的數據，再遍歷輸出右結點
• 后續遍歷 先遍歷輸出左結點，再遍歷輸出右結點，最后輸出當前結點的數據

2. 遞歸思想 想清楚子問題

3. 審題要全面 整體把握 分布思考清楚邊界

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第98题][验证二叉搜索树]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。