首页 > 代码库 > 【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?
题解:需要找到二叉搜索树中乱序的两个节点,并把它们交换回来。
排序二叉树的中序遍历得到的一定是一个递增序列,例如上述所示的BST,中序遍历得到的序列为1,3,5,9,11,15,20。假设错位的是3和11,那么错位后的树如下图所示
用遍历firstNode和secondNode表示错位的两个点,那么在中序遍历过程中,第一个错位点后面的点一定比它小(5比11小,11才是错位的点);第二个错位点一定比它前面的点小(3比9小)。采用递归的方法中序遍历BST,如果当前遍历的点root比它前面的点prev的值小,有两种可能,第一种是prev是第一个错位的点,此时firstNode变量为空,则将firstNode赋值为prev(代码中第24行);第二种是root是第二个错位的点,此时firstNode变量部位空,将secondNode变量赋值为root(代码中第22行)。
代码如下:
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 private TreeNode firstNode = null;12 private TreeNode secondNode = null;13 private TreeNode prev = null;14 15 private void traverse(TreeNode root){16 if(root == null)17 return;18 19 traverse(root.left);20 21 if(prev != null && root.val < prev.val){22 secondNode = root;23 if(firstNode == null)24 firstNode = prev;25 }26 prev = root;27 traverse(root.right);28 29 }30 31 public void recoverTree(TreeNode root) {32 traverse(root);33 34 int temp = firstNode.val;35 firstNode.val = secondNode.val;36 secondNode.val = temp;37 }38 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。