二叉树 LeetCode 刷题小结(五)

在上节的基础上，本节我们将继续汇总一些 LeetCode 有关二叉树的题。

接着上节，我们还是使用之前的程序框架，可以手动输入样例并测试，解题的方法不唯一。
所有题均来自于leetcode。

恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

图片.png

进阶:
使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？

我们知道二叉搜索树的中序遍历是一个递增序列，需要注意的是有两个节点被错误地交换了，那么我们在中序遍历时可以设置两个节点，遍历过程中要是有节点不满足升序，那么记录下来，遍历后交换这两个节点的值即可。
具体的程序如下：

// 99 恢复二叉搜索树
void recoverTree_helper(BiTree &root,BiTree &first,BiTree &second,BiTree &cur){
    if(root == nullptr){
        return ;
    }
    recoverTree_helper(root->left,first,second,cur);
    if(first == nullptr && stoi(cur->val) > stoi(root->val)){
        first = cur;
    }
    if(first != nullptr && stoi(cur->val) > stoi(root->val)){
        second = root;
    }
    cur = root;
    recoverTree_helper(root->right,first,second,cur);
}
void recoverTree(BiTree &root){
    BiTree first = nullptr;
    BiTree second = nullptr;
    int value_ = INT_MIN;
    BiTree cur = new BinaryNode(to_string(value_));
    recoverTree_helper(root,first,second,cur);
    swap(first->val,second->val);
}

测试程序：

int main(){
    //test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    recoverTree(tree);
    levelOrder(tree);
    return 0;
}

测试程序：

1
3 #
# 2
# #
3 1 2

3
1 4
# # 2 # #
# #
2 1 4 3

从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

图片.png

根据前序遍历和中序遍历的特点，我们可以使用前序数组中的元素分割中序数组，分割后递归处理 preorder 中的 cur 位置的元素 preorder[cur] ，以 preorder[cur] 为根的子树必然对应着 inorder 数组中 [left,right]之间的值。
一开始 cur = 0，以 preorder[0] 为根的树，对应着 inorder 数组中[0, inorder.size()-1] 之间的元素 preorder[0] 在 inorder 中的位置为 p，则将 inorder 数组分为 [0, p-1] 和 [p+1, inorder.size()-1] 两部分。
这两部分分别对应左子树的节点集合和右子树的节点集合。
因为先序数组中，左子树的节点全部在右子树的前面，所以 cur 值要传入到子树中处理后再传出的。

具体程序如下：

// 105 从前序与中序遍历序列构造二叉树
BiTree PI_buildTree_helper(vector<int>& preorder,int &cur, vector<int>& inorder,int left,int right){
    if(cur >= preorder.size()){
        return 0;
    }
    int index = left;
    for(index = left;index <= right;index++){
        if(preorder[cur] == inorder[index]){
            break;
        }
    }
    //根节点
    BiTree node = new BinaryNode(to_string(preorder[cur]));
    //左子树
    if(left <= index - 1){
        cur++;
        node->left = PI_buildTree_helper(preorder,cur,inorder,left,index - 1);
    }
    //右子树
    if(index + 1 <= right){
        cur++;
        node->right = PI_buildTree_helper(preorder,cur,inorder,index + 1,right);
    }
    return node;
}
BiTree PI_buildTree(vector<int>& preorder, vector<int>& inorder){
    int cur = 0;
    return PI_buildTree_helper(preorder,cur,inorder,0,inorder.size()-1);
}

测试程序：

int main(){
    //test
    //cout<<"test:......"<<endl;
    vector<int> preorder{3,9,20,15,7};
    vector<int> inorder{9,3,15,20,7};
    BiTree tree = PI_buildTree(preorder,inorder);
    levelOrder(tree);
    return 0;
}

测试结果：

3 9 20 15 7

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

图片.png

和上一题从前序与中序遍历序列构造二叉树的思路完全相同，
不同的是需要从后向前迭代后序数组，且先处理右子树，再处理左子树。

具体程序如下：

// 106 从中序与后序遍历序列构造二叉树
BiTree IP_buildTree_helper(vector<int>& postorder,int &cur, vector<int>& inorder,int left,int right){
    if(cur < 0 || left > right){
        return 0;
    }
    int index = left;
    for(index = left;index <= right;index++){
        if(postorder[cur] == inorder[index]){
            break;
        }
    }
    //根节点
    BiTree node = new BinaryNode(to_string(postorder[cur]));
    //右子树
    if(index + 1 <= right){
        cur--;
        node->right = IP_buildTree_helper(postorder,cur,inorder,index + 1,right);
    }
    //左子树
    if(left <= index - 1){
        cur--;
        node->left = IP_buildTree_helper(postorder,cur,inorder,left,index - 1);
    }
    return node;
}
BiTree IP_buildTree(vector<int>& inorder, vector<int>& postorder){
    int cur = inorder.size() - 1;
    return IP_buildTree_helper(postorder,cur,inorder,0,inorder.size() - 1);
}

测试程序如下：

int main(){
    //test
    //cout<<"test:......"<<endl;
    vector<int> inorder{9,3,15,20,7};
    vector<int> postorder{9,15,7,20,3};
    BiTree tree = IP_buildTree(inorder,postorder);
    levelOrder(tree);
    return 0;
}

测试结果：

3 9 20 15 7

二叉树的后序遍历

给定一个二叉树，返回它的后序遍历。

图片.png

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

后序遍历在之前的博客是提到过的，这里既然遇到了，那就再回顾下吧。

递归版

具体程序如下：

// 145 二叉树的后序遍历
void postorderTraversal_helper(BiTree root,vector<int> &res){
    if(root != NULL){
        postorderTraversal_helper(root->left,res);
        postorderTraversal_helper(root->right,res);
        res.push_back(stoi(root->val));
    }
}
vector<int> postorderTraversal(BiTree root){
    vector<int> res;
    postorderTraversal_helper(root,res);
    return res;
}

测试程序：

int main(){
    //test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    vector<int> res = postorderTraversal(tree);
    for(auto r : res){
        cout<<r<<" ";
    }
    cout<<endl;
    return 0;
}

测试结果：

1
# 2
3 #
# #
3 2 1

非递归版

需要两个栈来完成。
具体程序如下：

vector<int> postorderTraversal_(BiTree root){
    vector<int> res;
    if(root == NULL){
        return res;
    }
    stack<BiTree> s1;
    stack<BiTree> s2;
    s1.push(root);
    while(!s1.empty()){
        BiTree node = s1.top();
        s1.pop();
        s2.push(node);
        if(node->left){
            s1.push(node->left);
        }
        if(node->right){
            s1.push(node->right);
        }
    }
    while(!s2.empty()){
        res.push_back(stoi(s2.top()->val));
        s2.pop();
    }
    return res;
}

测试程序如下：

int main(){
    //test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    vector<int> res = postorderTraversal_(tree);
    for(auto r : res){
        cout<<r<<" ";
    }
    cout<<endl;
    return 0;
}

测试结果：

1
# 2
3 #
# #
3 2 1

二叉搜索树迭代器

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

图片.png

BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false

提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

时间复杂度是 $O(1)$ ，而空间复杂度是 $O(h)$ ，如果我们使用一个数组保存该树的中序遍历结果，时间复杂度可以满足，空间复杂度就不行了。
$O(h)$ 的空间复杂度意味着我们对于每一层树只能保存一个节点，而且还得在 $O(1)$ 时间内找到，一层只保存一个节点的话，我们可以保存最左边的节点，最小的肯定是最最左边的节点了，如果想知道下一个值，可以在该节点的父节点的右子树往左找，保存节点，最后一个那就是第二小的了，以此类推。
我们可以使用一个数据结构保存每一层节点，只要满足在一端添加，同一端去除元素即可，C++里面可以使用的有 stack，deque，vector等等。
那么三种我都使用了，时间上有一些差距，但是不明显。
这里以栈为例。

具体程序如下：

// 173 二叉搜索树迭代器
class BSTIterator{
public:
    stack<BiTree> storeNode;
    BSTIterator(BiTree root){
        while(root){
            storeNode.push(root);
            root = root->left;
        }
    }

    /** @return the next smallest number */
    int next(){
        BiTree node = storeNode.top();
        int ans = stoi(node->val);
        storeNode.pop();
        node = node->right;
        while(node){
            storeNode.push(node);
            node = node->left;
        }
        return ans;
    }

    /** @return whether we have a next smallest number */
    bool hasNext(){
        return !storeNode.empty();
    }

};

测试程序如下：

int main(){
    //test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    BSTIterator iterator_ = BSTIterator(tree);
    for(int i = 0;i < 5;i++){
        cout<<iterator_.next()<<" ";
        string res = "false";
        if(iterator_.hasNext()){
            res = "true";
        }
        cout<<res<<endl;
    }
    return 0;
}

测试结果：

7
3 15
# # 9 20
# # # #
3 true
7 true
9 true
15 true
20 false

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

图片.png

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

这个题可以利用二叉搜索树的性质来做，这样的父节点 root，应该满足 p->val < root->val，且 root->val < q->val。想到了这点，递归就完事了。
具体程序如下：

// 235 二叉搜索树的最近公共祖先
// 引入辅助函数寻找节点，假设节点存在于树中
BiTree lowestCommonAncestor_helper(BiTree root,int value){
    BiTree node = NULL;
    if(root == NULL){
        return root;
    }
    if(root->val == to_string(value)){
        return root;
    }else{
        node = lowestCommonAncestor_helper(root->left,value);
        if(node != NULL){
            if(node->val == to_string(value)){
                return node;
            }
        }
        node = lowestCommonAncestor_helper(root->right,value);
    }
    return node;
}
BiTree lowestCommonAncestor(BiTree root,BiTree p,BiTree q){
    if(root == NULL){
        return NULL;
    }
    //递归右子树
    if(stoi(q->val) > stoi(root->val) && stoi(p->val) > stoi(root->val)){
        return lowestCommonAncestor(root->right,p,q);
    }
    //递归左子树
    if(stoi(q->val) < stoi(root->val) && stoi(p->val) < stoi(root->val)){
        return lowestCommonAncestor(root->left,p,q);
    }
    return root;
}

测试程序如下：

int main(){
    //test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    int value_p;
    cin>>value_p;
    BiTree p = lowestCommonAncestor_helper(tree,value_p);
    int value_q;
    cin>>value_q;
    BiTree q = lowestCommonAncestor_helper(tree,value_q);
    cout<<lowestCommonAncestor(tree,p,q)->val;
    return 0;
}

测试结果：

6
2 8
0 4 7 9
# # 3 5 # # # #
# # # #
2 8
6

6
2 8
0 4 7 9
# # 3 5 # # # #
# # # #
2 4
2

二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

图片.png

这个题相对比较简单，先保存节点的值，遇到叶子节点，意味着走到头了，保存路径；否则递归左右子树，还得记得加上"->"。
具体程序如下：

// 257 二叉树的所有路径
void binaryTreePaths_helper(BiTree root,string path,vector<string> &data){
    if(root != NULL){
        path += root->val;
        // 叶子节点
        if((root->left == NULL) && (root->right == NULL)){
            data.push_back(path);
            path = "";
        }else{
            path += "->";
            binaryTreePaths_helper(root->left,path,data);
            binaryTreePaths_helper(root->right,path,data);
        }
    }
}
vector<string> binaryTreePaths(BiTree root){
    vector<string> data;
    binaryTreePaths_helper(root,"",data);
    return data;
}

测试程序：

int main(){
    //test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    vector<string> data = binaryTreePaths(tree);
    for(auto d : data){
        cout<<d<<endl;
    }
    return 0;
}

测试结果：

1
2 3
# 5 # #
# #
1->2->5
1->3

全部代码见 github ，main.cpp 中不带测试程序。
本节内容到此结束，之后将继续更新。

最后编辑于：2020.02.26 17:37:18

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,491评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,856评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,745评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,196评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,073评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,112评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,531评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,215评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,485评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,578评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,356评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,215评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,583评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,898评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,174评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,497评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,697评论 2赞 335

二叉树 LeetCode 刷题小结(五)

恢复二叉搜索树

从前序与中序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

二叉树的后序遍历

递归版

非递归版

二叉搜索树迭代器

二叉搜索树的最近公共祖先

二叉树的所有路径

推荐阅读更多精彩内容