首页 > 代码库 > LeetCode Recover Binary Search Tree

LeetCode Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

 

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

 

 1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11 12 13     TreeNode n1 = null;14     TreeNode n2 = null;15     TreeNode pre = null;16 17     public void recoverTree(TreeNode root) {18         findNodes(root);19         if (n1 != null && n2 != null) {20             int temp = n1.val;21             n1.val = n2.val;22             n2.val = temp;23         }24     }25 26     void findNodes(TreeNode root) {27         if (root == null) {28             return;29         }30         findNodes(root.left);31         if (pre != null && pre.val > root.val) {32             if (n1 == null) {33                 n1 = pre;34             }35             n2 = root;36         }37         pre = root;38         findNodes(root.right);39     }40 41 42 }

 

LeetCode Recover Binary Search Tree