一、題目
1、審題
?
? 2、分析
給出一個二叉查找樹，其中有兩個元素的位置弄錯了，寫算法將其恢復。
?
二、解答
1、思路：
方法一、
通過中序遍歷可以確定一棵二叉查找樹由小到大的順序。
所以在此錯位的查找樹中查找到的節點中有 1?個比后續節點值大，最后 1?個比前面相鄰節點值小。交換這兩個結點值即可。
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; // 記錄第一個比后續元素大的那個結點if(firstElement != null && prevElement.val >= root.val)secondElement = root; // 記錄最后一個比前一個結點小的節點。 prevElement = root; // 要查找的節點指針往后移動/// traverse(root.right);}
?
方法)
