写点什么

手撸二叉树之恢复二叉树

发布于: 4 小时前
手撸二叉树之恢复二叉树

Hello, 大家好,今天是我参加 9 月更文的第 10 天,今天给大家带来的关于二叉树相关的算法题是二叉树的左叶子之和,正文如下:


题目

给你二叉搜索树的根节点 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<TreeNode> 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)。我们需要用数组存储树的中序遍历列表。

发布于: 4 小时前阅读数: 2
用户头像

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

评论

发布
暂无评论
手撸二叉树之恢复二叉树