一、題目

　　1、審題

?

?　　2、分析

　　　　給出一個二叉查找樹，其中有兩個元素的位置弄錯了，寫算法將其恢復(fù)。

?

二、解答

　　1、思路：

　　　　方法一、

　　　　　　通過中序遍歷可以確定一棵二叉查找樹由小到大的順序。

　　　　　　所以在此錯位的查找樹中查找到的節(jié)點中有 1?個比后續(xù)節(jié)點值大，最后 1?個比前面相鄰節(jié)點值小。交換這兩個結(jié)點值即可。

　　TreeNode firstElement = null;TreeNode secondElement = null;TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);public void recoverTree(TreeNode root) {traverse(root);int tmp = firstElement.val;firstElement.val = secondElement.val;secondElement.val = tmp; }private void traverse(TreeNode root) {if(root == null)return;traverse(root.left);///if(firstElement == null && prevElement.val >= root.val)firstElement = prevElement; // 記錄第一個比后續(xù)元素大的那個結(jié)點if(firstElement != null && prevElement.val >= root.val)secondElement = root; // 記錄最后一個比前一個結(jié)點小的節(jié)點。 prevElement = root; // 要查找的節(jié)點指針往后移動/// traverse(root.right);}

?

轉(zhuǎn)載于:https://www.cnblogs.com/skillking/p/9711950.html

總結(jié)

以上是生活随笔為你收集整理的99. Recover Binary Search Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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