重温数据结构之二叉树：恢复二叉搜索树

重温数据结构之二叉树：恢复二叉搜索树

题目

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

示例1：

输入：root = [1,3,null,null,2]输出：[3,1,null,null,2]解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3

示例2：

输入：root = [3,1,4,null,null,2]输出：[2,1,4,null,null,3]解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3

解决思路

根据题意可知，是二叉搜索树，这就是意味着节点之间是有顺序关系的。 如果我们把整棵树都 遍历 一遍，将遍历的结果保存下来，比如放到一个数组中。 那么这个数组应该是有序的。

既然是有序的那就好办了，我们将这个有序的数组遍历一遍。 如果数组是完全有序的，那么直接返回就可以了。 否则，我们找到顺序不一致的两个下标i和j，将arr[i].val和arr[j].val的值互换一下即可。

代码实现

/** * Definition for a binary tree node. * public 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; * } * } */class Solution { public List list; public void recoverTree(TreeNode root) { list = new ArrayList(); inOrder(root); TreeNode x = null; TreeNode y = null; for (int i = 0; i < list.size() - 1; i++) { if (list.get(i).val > list.get(i+1).val){ y = list.get(i+1); if (x == null) { x = list.get(i); } } } if (x != null && y != null) { int tmp = x.val; x.val = y.val; y.val = tmp; } } public void inOrder(TreeNode root) { if (root == null) return; inOrder(root.left); list.add(root); inOrder(root.right);

最后

复杂度分析：

时间复杂度：O(N)，其中 N 为二叉搜索树的节点数。中序遍历需要 O(N) 的时间，判断两个交换节点在最好的情况下是 O(1)，在最坏的情况下是 O(N)，因此总时间复杂度为 O(N)。空间复杂度：O(N)。我们需要用 数组存储树的中序遍历列表

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。