美文网首页刷题总结
二叉树 LeetCode 刷题小结(五)

二叉树 LeetCode 刷题小结(五)

作者: 思想永不平凡 | 来源:发表于2020-02-17 17:48 被阅读0次

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

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

恢复二叉搜索树

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

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

图片.png 图片.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 中不带测试程序。
本节内容到此结束，之后将继续更新。

相关文章

网友评论

    本文标题：二叉树 LeetCode 刷题小结(五)

    本文链接：https://www.haomeiwen.com/subject/kaubfhtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    刷题总结

    关于我们|服务条款|联系我们|二叉树 LeetCode 刷题小结(五)|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！