恢複二叉搜尋樹
題目
給你二叉搜尋樹的根節點 root ，該樹中的兩個節點被錯誤地交換。請在不改變其結構的情況下，恢複這棵樹。
示例1：
輸入：root = [1,3,null,null,2]
輸出：[3,1,null,null,2]
解釋：3 不能是 1 左孩子，因為 3 > 1 。交換 1 和 3 示例2：
輸入：root = [3,1,4,null,null,2]
輸出：[2,1,4,null,null,3]
解釋：2 不能在 3 的右子樹中，因為 2 < 3 。交換 2 和 3 解決思路
根據題意可知，是二叉搜尋樹，這就是意味着節點之間是有順序關系的。
如果我們把整棵樹都 周遊 一遍，将周遊的結果儲存下來，比如放到一個數組中。
那麼這個數組應該是有序的。
既然是有序的那就好辦了，我們将這個有序的數組周遊一遍。
如果數組是完全有序的，那麼直接傳回就可以了。
否則，我們找到順序不一緻的兩個下标i和j，将arr[i].val和arr[j].val的值互換一下即可。
代碼實作
/**
* Definition for a binary tree node.
* 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 {
public List<TreeNode> list;
public void recoverTree(TreeNode root) {
list = new ArrayList();
inOrder(root);
TreeNode x = null;
TreeNode y = null;
for (int i = 0; i < list.size() - 1; i++) {
if (list.get(i).val > list.get(i+1).val){
y = list.get(i+1);
if (x == null) {
x = list.get(i);
}
}
}
if (x != null && y != null) {
int tmp = x.val;
x.val = y.val;
y.val = tmp;
}
}
public void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
list.add(root);
inOrder(root.right); 複雜度分析
- 時間複雜度：O(N)，其中 N 為二叉搜尋樹的節點數。中序周遊需要 O(N) 的時間，判斷兩個交換節點在最好的情況下是 O(1)，在最壞的情況下是 O(N)，是以總時間複雜度為 O(N)。
- 空間複雜度：O(N)。我們需要用 數組存儲樹的中序周遊清單
驗證二叉搜尋樹
題目
給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜尋樹。
有效 二叉搜尋樹定義如下：
- 節點的左子樹隻包含 小于 目前節點的數。
- 節點的右子樹隻包含 大于 目前節點的數。
- 所有左子樹和右子樹自身必須也是二叉搜尋樹。
示例1：
示例2：
解題思路
代碼實作
/**
* Definition for a binary tree node.
* 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 {
public long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)){
return false;
}
if (root.val <= pre) {
return false;
}
pre = root.val;
return isValidBST(root.right); 複雜度分析
- 時間複雜度 : O(n)，其中 n 為二叉樹的節點個數。二叉樹的每個節點最多被通路一次，是以時間複雜度為 O(n)。
- 空間複雜度 : O(n)，其中 n 為二叉樹的節點個數。棧最多存儲 n 個節點，是以需要額外的 O(n) 的空間。