国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > php教程 > 【Leetcode】Recover Binary Search Tree

【Leetcode】Recover Binary Search Tree

来源:程序员人生   发布时间:2016-06-04 08:46:50 阅读次数:641次

题目链接:https://leetcode.com/problems/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?

思路:

1.中序 保存所有结点  空间复杂度O(n)

2.中序递归 保存前1个结点的指针 找到不对的结点

算法:

public void recoverTree(TreeNode root) { inorder(root); if (third != null) {// 2次逆序 int tmp = first.val; first.val = third.val; third.val = tmp; } else {// 1次逆序 int tmp = second.val; second.val = first.val; first.val = tmp; } } TreeNode pre, first, second, third; public void inorder(TreeNode root) { if (root == null) return; inorder(root.left); if (pre == null) { pre = root; } else { if (root.val < pre.val) { if (first == null) { // 如果第1次逆序 需要交换first和second结点 first = pre; second = root; } else {// 如果第2次逆序 只需要交换first和third结点 third = root; } } } pre = root; inorder(root.right); }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生