给你二叉搜索树的根节点 root ,该树中的两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution { public void recoverTree(TreeNode root) { if (root == null) { return; } TreeNode first = null, second = null; TreeNode pre = null, cur = root; while (cur != null) { TreeNode mostRight = cur.left; if (mostRight != null) { while (mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } if (mostRight.right == null) { mostRight.right = cur; cur = cur.left; continue; } else { mostRight.right = null; } } if (pre != null && pre.val > cur.val) { if (first == null) { first = pre; second = cur; } else { second = cur; } } pre = cur; cur = cur.right; } swap(first, second); } public void swap(TreeNode a, TreeNode b) { int t = a.val; a.val = b.val; b.val = t; } } 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; } }