C++实现LeetCode(99.复原二叉搜索树)

[LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

   1
/
3
\
2

Output: [3,1,null,null,2]

   3
/
1
\
2

Example 2:

Input: [3,1,4,null,null,2]

3
/ \
1   4
/
2

Output: [2,1,4,null,null,3]

  2
/ \
1   4
/
3

Follow up:

  • A solution using O(n) space is pretty straight forward.
  • Could you devise a constant space solution?

这道题要求我们复原一个二叉搜索树,说是其中有两个的顺序被调换了,题目要求上说 O(n) 的解法很直观,这种解法需要用到递归,用中序遍历树,并将所有节点存到一个一维向量中,把所有节点值存到另一个一维向量中,然后对存节点值的一维向量排序,在将排好的数组按顺序赋给节点。这种最一般的解法可针对任意个数目的节点错乱的情况,这里先贴上此种解法:

解法一:

// O(n) space complexity
class Solution {
public:
    void recoverTree(TreeNode* root) {
        vector<TreeNode*> list;
        vector<int> vals;
        inorder(root, list, vals);
        sort(vals.begin(), vals.end());
        for (int i = 0; i < list.size(); ++i) {
            list[i]->val = vals[i];
        }
    }
    void inorder(TreeNode* root, vector<TreeNode*>& list, vector<int>& vals) {
        if (!root) return;
        inorder(root->left, list, vals);
        list.push_back(root);
        vals.push_back(root->val);
        inorder(root->right, list, vals);
    }
};

然后博主上网搜了许多其他解法,看到另一种是用双指针来代替一维向量的,但是这种方法用到了递归,也不是 O(1) 空间复杂度的解法,这里需要三个指针,first,second 分别表示第一个和第二个错乱位置的节点,pre 指向当前节点的中序遍历的前一个节点。这里用传统的中序遍历递归来做,不过在应该输出节点值的地方,换成了判断 pre 和当前节点值的大小,如果 pre 的大,若 first 为空,则将 first 指向 pre 指的节点,把 second 指向当前节点。这样中序遍历完整个树,若 first 和 second 都存在,则交换它们的节点值即可。这个算法的空间复杂度仍为 O(n),n为树的高度,参见代码如下:

解法二:

// Still O(n) space complexity
class Solution {
public:
    TreeNode *pre = NULL, *first = NULL, *second = NULL;
    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(first->val, second->val);
    }
    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        if (!pre) pre = root;
        else {
            if (pre->val > root->val) {
                if (!first) first = pre;
                second = root;
            }
            pre = root;
        }
        inorder(root->right);
    }
};

我们其实也可以使用迭代的写法,因为中序遍历 Binary Tree Inorder Traversal 也可以借助栈来实现,原理还是跟前面的相同,记录前一个结点,并和当前结点相比,如果前一个结点值大,那么更新 first 和 second,最后交换 first 和 second 的结点值即可,参见代码如下:

解法三:

// Always O(n) space complexity
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *pre = NULL, *first = NULL, *second = NULL, *p = root;
        stack<TreeNode*> st;
        while (p || !st.empty()) {
            while (p) {
                st.push(p);
                p = p->left;
            }
            p = st.top(); st.pop();
            if (pre) {
                if (pre->val > p->val) {
                    if (!first) first = pre;
                    second = p;
                }
            }
            pre = p;
            p = p->right;
        }
        swap(first->val, second->val);
    }
};

这道题的真正符合要求的解法应该用的 Morris 遍历,这是一种非递归且不使用栈,空间复杂度为 O(1) 的遍历方法,可参见博主之前的博客 Binary Tree Inorder Traversal,在其基础上做些修改,加入 first, second 和 parent 指针,来比较当前节点值和中序遍历的前一节点值的大小,跟上面递归算法的思路相似,代码如下:

解法四:

// Now O(1) space complexity
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *cur = root, *pre = nullptr ;
        while (cur) {
            if (cur->left){
                TreeNode *p = cur->left;
                while (p->right && p->right != cur) p = p->right;
                if (!p->right) {
                    p->right = cur;
                    cur = cur->left;
                    continue;
                } else {
                    p->right = NULL;
                }
            }
            if (pre && cur->val < pre->val){
              if (!first) first = pre;
              second = cur;
            }
            pre = cur;
            cur = cur->right;
        }
        swap(first->val, second->val);
    }
};

到此这篇关于C++实现LeetCode(99.复原二叉搜索树)的文章就介绍到这了,更多相关C++实现复原二叉搜索树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-17

C++实现LeetCode(137.单独的数字之二)

[LeetCode] 137. Single Number II 单独的数字之二 Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you

C++实现LeetCode(136.单独的数字)

[LeetCode] 136.Single Number 单独的数字 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

C++实现LeetCode(91.解码方法)

[LeetCode] 91. Decode Ways 解码方法 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to

C++实现LeetCode(187.求重复的DNA序列)

[LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Wr

C++实现LeetCode(96.独一无二的二叉搜索树)

[LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树 Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1         3  

C++实现LeetCode(95.独一无二的二叉搜索树之二)

[LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二 Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3],

C++实现LeetCode(94.二叉树的中序遍历)

[LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历 Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively

C++实现LeetCode(93.复原IP地址)

[LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 这

Java实现复原IP地址的方法

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式. 示例: 输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"] PS: 跪了,得LeetCode者得天下,上次我学的位运算符,这次学的ip地址 class Solution { private List<String> res = new ArrayList<>(); public List&

python 输入字符串生成所有有效的IP地址(LeetCode 93号题)

这题的官方难度是Medium,点赞1296,反对505,通过率35.4%.从各项指标来说看起来有些中规中矩,实际上也的确如此.这道题的解法和立意都有些显得新意不足,但总体来说题目的质量还是可以的,值得一做. 题意 给定一个由数字组成的字符串,我们希望通过这个字符串得到所有有效ip地址的组合.对于一个有效的ip地址而言,它应该有4个数字组成,每一个数字的范围在0到255之间. 一个字符串可能可以转化成多个ip地址,我们需要存储下来所有可以成立的情况. 样例 Input: "25525511135&

SunTB编写IP地址设置切换批处理

修正一个提取网络连接名称的错误,原因在于之前在FOR中使用空格作为分隔符 如果网络连接名为"本地连接 2",原来只会识别成"本地连接",从而导致设置失败 现已更正 说明:1.可以选择要设置的网络连接 2.可以手动设定固定IP,也可以通过DHCP自动获取 3.可以在批处理中预设多组MAC与IP对应数据,当内网有MAC绑定时可快速查询相应IP 4.DNS设置提供四类数据(中国电信. 中国联通/中国网通.中国移动/ 国铁通.内网网关) DNS为福州地区数据,请自行更改为当

IP地址正则表达式匹配方法

正则表达式(Regular Expression,在代码中常简写为regex.regexp或RE)是计算机科学的一个概念.正则表达式使用单个字符串来描述.匹配一系列符合某个句法规则的字符串.在很多文本编辑器里,正则表达式通常被用来检索.替换那些符合某个模式的文本.许多程序设计语言都支持利用正则表达式进行字符串操作.在很多文本编辑器里,正则表达式通常被用来检索.替换那些符合某个模式的文本. 正则表达式 ^(25[0-5]|2[0-4][0-9]|[0-1]{1}[0-9]{2}|[1-9]{1}[

最全正则表达式总结:验证QQ号、手机号、Email、中文、邮编、身份证、IP地址等

什么是 RegExp? RegExp 是正则表达式(Regular expression)的缩写,作用是对字符串执行模式匹配. 通常用于格式验证.正则替换.查找子串等 各种编程语言的正则表达式基本相同,不同的语言可能会有一些细小的差别 RegExp 语法 1.// 直接实例化 2.var reg = new RegExp(pattern [, flags]) 3.// 隐式创建(推荐) 4.var reg = /pattern/flags; 参数 pattern 是一个字符串,指定了正则表达式的

使用CDN之后APACHE日志记录中IP地址不正确的解决方案

最近在搞APACHE日志分析,装好了awstats之后,这两天进行了观察, 报表日期 月 1 月 2010 首次参观日期 2010年01月12日 11:04 最近参观日期 2010年01月13日 23:59     参观者 参观人次 网页数 文件数 字节 浏览器流量 * 77  226  (2.93 参观人次/参观者) 508979 (2252.11 网页数/参观) 509492 (2254.38 文件数/参观) 13.67 G字节 (63430.28 K字节/参观) 非浏览器流量 *  117

Google打不开的解决方法和IP地址表

本文将给出一些能够正常访问被屏蔽的Google搜索引擎的常用方法以及Google的IP地址表. 在Google.com里面进行搜索的时候,经常会遇到突然出现"该页无法显示"的提示,并且之后的十多分钟都无法正常连接Google,这里给出一些方法,可以解决大部分Google无法访问或进不去的问题. 1.如果是搜索过程中出现"该页无法显示"的提示,接着就无法访问Google,那么对于ADSL用户,可以尝试断开网络连接,然后重新拨号上网,这样你的IP地址就发生了变化,这时候

为VMware的多台虚拟机绑定IP地址的方法

最近我在VMware上面用三台虚拟机搭建了一个hadoop的集群.但是后来发现了一个问题:每次重新打开三台机器的时候,因为主机所连接的网络的变化,会导致VMware中的这三台虚拟机的IP地址也变掉.这会导致ssh失败,三台机器无法通讯.所以总结了一种方式来绑定虚拟机的IP地址. 1.打开虚拟机后,在编辑>模拟网络编辑器>NET设置中查看自己的IP地址.子网掩码.和网关. 2.开启虚拟机服务 我的电脑--> 管理 -->服务和应用程序-->服务 (这个一般情况下我们的电脑都已经

命令行实现MAC与IP地址绑定 ip mac绑定 如何绑定mac地址

为什么要绑定IP呢?你指定的IP能上外网不就可以了吗?之所以要绑定IP,是因为他会会改IP.比如我本机上的IP是192.168.1.11此IP已经在防火墙上面做了设定不可以上网,但我要是知道有一个IP是192.168.1.30的IP能上网,那我不会改把192.168.1.11换成192.168.1.30就可以上网了吗?所以绑定IP就是为了防止他改IP. 因为网卡的MAC地址是全球唯一的跟我们的身份证一样,他一但改了,就不认了.那如何绑定呢? 例如我的IP是192.168.1.11,网卡的MAC地

java获取ip地址示例

如果使用了反向代理软件,将http://192.168.1.110:2046/ 的URL反向代理为http://www.xxx.com/ 的URL时,用request.getRemoteAddr()方法获取的IP地址是:127.0.0.1 或 192.168.1.110,而并不是客户端的真实IP. 经过代理以后,由于在客户端和服务之间增加了中间层,因此服务器无法直接拿到客户端的IP,服务器端应用也无法直接通过转发请求的地址返回给客户端.但是在转发请求的HTTP头信息中,增加了X-FORWARDE