Leetcode 恢復(fù)二叉搜索樹(shù)

image.png

分析：
首先題目壽命恰好存在兩個(gè)錯(cuò)誤節(jié)點(diǎn)；因?yàn)槎嫠阉鳂?shù)的中序遍歷一定是有序的，那么原有問(wèn)題就轉(zhuǎn)化為該有序的數(shù)組，一定存在兩個(gè)點(diǎn)是錯(cuò)誤的，我們只需要找出這兩個(gè)點(diǎn)，并且交換對(duì)應(yīng)的值就可以解決這個(gè)問(wèn)題。

那么我們要如何找到這兩個(gè)錯(cuò)誤位置呢？它會(huì)存在如下三種情況：

• 情況1： 這兩個(gè)錯(cuò)誤的位置在左子樹(shù)
• 情況2： 這兩個(gè)錯(cuò)誤的位置在右子樹(shù)
• 情況3：這兩個(gè)錯(cuò)誤的位置橫叉在兩邊

根據(jù)這種方式：我們按照如下的思路進(jìn)行題解編碼：
（1） 首先按照遞歸深度優(yōu)先遍歷，將二叉樹(shù)轉(zhuǎn)為L(zhǎng)ist數(shù)組
（2） 找出根節(jié)點(diǎn)的索引位置
（3） 聲明LLeft,LRight,RLeft,RRight，分別代表左子樹(shù)的待交換的值，以及右子樹(shù)待交換的值。根據(jù)根節(jié)點(diǎn)索引計(jì)算出這四個(gè)值出來(lái)
（4）針對(duì)這4個(gè)值得邏輯判斷：

if (LLeft != -1 && RRight != -1) {
                swap(LLeft,RRight, nodesList);
            } else if (LLeft != -1 && RRight == -1) {
                swap(LLeft,LRight,nodesList);
            } else if (RRight != -1 && LLeft == -1) {
                swap(RLeft,RRight, nodesList);
            }

那么最終的代碼實(shí)現(xiàn)如下：

/**
 * 題目Id：99
 * 題目：恢復(fù)二叉搜索樹(shù)
 * 內(nèi)容: //給你二叉搜索樹(shù)的根節(jié)點(diǎn) root ，該樹(shù)中的 恰好 兩個(gè)節(jié)點(diǎn)的值被錯(cuò)誤地交換。請(qǐng)?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下，恢復(fù)這棵樹(shù) 。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //輸入：root = [1,3,null,null,2]
 * //輸出：[3,1,null,null,2]
 * //解釋：3 不能是 1 的左孩子，因?yàn)?3 > 1 。交換 1 和 3 使二叉搜索樹(shù)有效。
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //輸入：root = [3,1,4,null,null,2]
 * //輸出：[2,1,4,null,null,3]
 * //解釋：2 不能在 3 的右子樹(shù)中，因?yàn)?2 < 3 。交換 2 和 3 使二叉搜索樹(shù)有效。
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 樹(shù)上節(jié)點(diǎn)的數(shù)目在范圍 [2, 1000] 內(nèi)
 * // -231 <= Node.val <= 231 - 1
 * //
 * //
 * //
 * //
 * // 進(jìn)階：使用 O(n) 空間復(fù)雜度的解法很容易實(shí)現(xiàn)。你能想出一個(gè)只使用 O(1) 空間的解決方案嗎？
 * // Related Topics 樹(shù) 深度優(yōu)先搜索 二叉搜索樹(shù) 二叉樹(shù) ?? 771 ?? 0
 * <p>
 * 日期：2022-08-28 21:54:42
 */
//給你二叉搜索樹(shù)的根節(jié)點(diǎn) root ，該樹(shù)中的 恰好 兩個(gè)節(jié)點(diǎn)的值被錯(cuò)誤地交換。請(qǐng)?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下，恢復(fù)這棵樹(shù) 。
//
//
//
// 示例 1：
//
//
//輸入：root = [1,3,null,null,2]
//輸出：[3,1,null,null,2]
//解釋：3 不能是 1 的左孩子，因?yàn)?3 > 1 。交換 1 和 3 使二叉搜索樹(shù)有效。
//
//
// 示例 2：
//
//
//輸入：root = [3,1,4,null,null,2]
//輸出：[2,1,4,null,null,3]
//解釋：2 不能在 3 的右子樹(shù)中，因?yàn)?2 < 3 。交換 2 和 3 使二叉搜索樹(shù)有效。
//
//
//
// 提示：
//
//
// 樹(shù)上節(jié)點(diǎn)的數(shù)目在范圍 [2, 1000] 內(nèi)
// -231 <= Node.val <= 231 - 1
//
//
//
//
// 進(jìn)階：使用 O(n) 空間復(fù)雜度的解法很容易實(shí)現(xiàn)。你能想出一個(gè)只使用 O(1) 空間的解決方案嗎？
// Related Topics 樹(shù) 深度優(yōu)先搜索 二叉搜索樹(shù) 二叉樹(shù) ?? 771 ?? 0

package leetcode.editor.cn;

import common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class P99RecoverBinarySearchTreeV2 {
    public static void main(String[] args) {
        Solution solution = new P99RecoverBinarySearchTreeV2().new Solution();
        System.out.println("Hello world");
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 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 void recoverTree(TreeNode root) {
            List<TreeNode> nodesList = new ArrayList<>();
            traversalNodeTree(root, nodesList);
            int rootIndex = -1;
            for (int i = 0; i < nodesList.size(); i++) {
                if (nodesList.get(i).val == root.val) {
                    rootIndex = i;
                    break;
                }
            }
            int LLeft = -1;
            int LRight = rootIndex;
            for (int i = 0; i < rootIndex; i++) {
                if (nodesList.get(i).val > nodesList.get(i + 1).val) {
                    LLeft = i;
                    break;
                }
            }
            for (int j = rootIndex; j >= 1; j--) {
                if (nodesList.get(j).val < nodesList.get(j - 1).val) {
                    LRight = j;
                    break;
                }
            }
            int RLeft = rootIndex;
            int RRight = -1;
            for (int i = rootIndex; i < nodesList.size() - 1; i++) {
                if (nodesList.get(i).val > nodesList.get(i + 1).val) {
                    RLeft = i;
                    break;
                }
            }
            for (int j = nodesList.size() - 1; j >= rootIndex + 1; j--) {
                if (nodesList.get(j).val < nodesList.get(j - 1).val) {
                    RRight = j;
                    break;
                }
            }
            if (LLeft != -1 && RRight != -1) {
                swap(LLeft,RRight, nodesList);
            } else if (LLeft != -1 && RRight == -1) {
                swap(LLeft,LRight,nodesList);
            } else if (RRight != -1 && LLeft == -1) {
                swap(RLeft,RRight, nodesList);
            }
        }

        private void swap(int leftNotValidIndex, int rightNotValidIndex, List<TreeNode> nodesList) {
            int temp = nodesList.get(leftNotValidIndex).val;
            nodesList.get(leftNotValidIndex).val = nodesList.get(rightNotValidIndex).val;
            nodesList.get(rightNotValidIndex).val = temp;
        }


        private void traversalNodeTree(TreeNode root, List<TreeNode> nodesList) {
            if (root == null) {
                return;
            }
            if (root.left != null) {
                traversalNodeTree(root.left, nodesList);
            }
            nodesList.add(root);

            if (root.right != null) {
                traversalNodeTree(root.right, nodesList);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}