重溫資料結構之二叉樹：恢複二叉搜尋樹

題目

給你二叉搜尋樹的根節點 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      

解決思路

代碼實作

/**
 * 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)。我們需要用 數組存儲樹的中序周遊清單

1. 關注公衆号---​​HelloWorld傑少​​