root 是一棵錯(cuò)誤的二叉搜索樹（有2個(gè)節(jié)點(diǎn)被錯(cuò)誤交換）

發(fā)生在逆序?qū)Φ念^，尾這兩個(gè)位置

第2個(gè)錯(cuò)誤節(jié)點(diǎn)：最后一個(gè)逆序?qū)χ休^小的那個(gè)節(jié)點(diǎn) second

/*** 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 {// 中序遍歷：時(shí)間復(fù)雜度O(n)、空間復(fù)雜度O(1)/*** 上一次中序遍歷過的節(jié)點(diǎn)*/private TreeNode prev;/*** 第一個(gè)錯(cuò)誤節(jié)點(diǎn)*/private TreeNode first;/*** 第二個(gè)錯(cuò)誤節(jié)點(diǎn)*/private TreeNode second;private void find(TreeNode node) {// 出現(xiàn)了逆序?qū)f (prev != null && prev.val > node.val) {// 第2個(gè)錯(cuò)誤節(jié)點(diǎn)：最后一個(gè)逆序?qū)χ休^小的那個(gè)節(jié)點(diǎn)second = node;// 第1個(gè)錯(cuò)誤節(jié)點(diǎn)：第一個(gè)逆序?qū)χ休^大的那個(gè)節(jié)點(diǎn)if (first != null) return;first = prev;}prev = node;}/*** @param root 是一棵錯(cuò)誤的二叉搜索樹（有2個(gè)節(jié)點(diǎn)被錯(cuò)誤交換）*/public void recoverTree(TreeNode root) {findWrongNodes(root);// 交換2個(gè)錯(cuò)誤節(jié)點(diǎn)的值int tmp = first.val;first.val = second.val;second.val = tmp;}private void findWrongNodes(TreeNode root) {if (root == null) return;findWrongNodes(root.left);find(root);findWrongNodes(root.right);} }

?

總結(jié)

以上是生活随笔為你收集整理的99. 恢复二叉搜索树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。