首页 > 代码库 > Recover Binary Search Tree

Recover Binary Search Tree

2024-07-27 16:50:31   220人阅读

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? 


OJ‘s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#‘ signifies a path terminator where no node exists below.

Here‘s an example:

   1
  /  2   3
    /
   4
         5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

答案

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode a=null;
    TreeNode b=null;
    TreeNode pre;
    public void recover(TreeNode root)
    {
        if(root!=null)
        {
            recover(root.left);
            if(pre.val>root.val)
            {
                if(a==null)
                {
                    a=pre;
                }
                b=root;
            }
            pre=root;
            recover(root.right);
        }
    }
    public void recoverTree(TreeNode root) {
        pre=new TreeNode(Integer.MIN_VALUE);
        recover(root);
        if(a!=null)
        {
            int p=a.val;
            a.val=b.val;
            b.val=p;
        }
    }
}


Recover Binary Search Tree


联系
我们