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

二叉树 LeetCode 刷题小结(二)

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

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

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

    翻转二叉树

    翻转一棵二叉树。

    图片.png

    这个题需要我们翻转二叉树，可以用递归来实现。
    当一个节点为空，需不需要交换都无所谓；当其不为空时，交换该节点的左右子树即可，继续递归其左右子树，只要遍历到每一个节点就可以了，遍历到该节点，就换交换其左右子树，以什么方式遍历的其实无所谓。
    简单来说就是，每一个节点做好自己的事情：交换该节点的左右子树。每个节点做好这件事，再顾及到每个节点，二叉树就翻转成功了。

    具体的程序如下：

    //226 翻转二叉树
BiTree invertTree(BiTree root){
    if(root == NULL){
        return NULL;
    }
    BiTree r = invertTree(root->right);
    BiTree l = invertTree(root->left);

    root->left = r;
    root->right = l;
    return root;
}

    测试程序：

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

    测试结果为：

    4
2 7
1 3 6 9
# # # # # # # #
4 7 2 9 6 3 1

    左叶子之和

    计算给定二叉树的所有左叶子之和。

    图片.png

    这个题首先要明确什么是左叶子，节点为空，不操作，若一个节点是左叶子，取它的值相加，之和明确什么时候递归左子树，右子树，这个问题就不难了。

    具体程序：

    // 404 左叶子之和
void sumOfLeftLeaves_helper(BiTree root,int& sum){
    if(root == NULL){
        sum = sum;
    }else{
        if(root->left != NULL){
            // 左叶子的条件
            if(root->left->left == NULL && root->left->right == NULL){
                sum += stoi(root->left->val);
            }else{
                sumOfLeftLeaves_helper(root->left,sum);
            }
            if(root->right != NULL){
                sumOfLeftLeaves_helper(root->right,sum);
            }
        }
    }
}
int sumOfLeftLeaves(BiTree root){
    int sum = 0;
    sumOfLeftLeaves_helper(root,sum);
    return sum;
}

    测试程序：

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

    测试结果：

    3 
9 20
# # 15 7
# # # #
24

    二叉树的中序遍历

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

    图片.png

    这个，我在之前的博客《二叉树常见操作的 C++ 实现(一)》，介绍过递归与非递归的前，中，后序遍历以及层次遍历。
    这里，我们再回顾一下吧。

    递归版

    递归版的很简单。
    具体程序如下：

    // 94 二叉树的中序遍历,递归版
void inorderTraversal_helper(BiTree root,vector<int>& res){
    if(root == NULL){
        return ;
    }
    inorderTraversal_helper(root->left,res);
    res.push_back(stoi(root->val));
    inorderTraversal_helper(root->right,res);
}
vector<int> inorderTraversal(BiTree root){
    vector<int> res;
    inorderTraversal_helper(root,res);
    return res;
}

    测试程序如下：

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

    测试结果：

    1
# 2
3 #
# #
1 3 2

    非递归版

    具体程序如下：

    // 94 二叉树的中序遍历,非递归版
vector<int> inorderTraversal_(BiTree root){
    stack<BiTree> m;
    vector<int> res;
    BiTree rt = root;
    while(rt != NULL|| m.size() != 0){
        while(rt != NULL){
            m.push(rt);
            rt = rt->left;
        }
        rt = m.top();
        m.pop();
        res.push_back(stoi(rt->val));
        rt = rt->right;
    }
    return res;
}

    测试程序：

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

    测试结果：

    1
# 2
3 #
# #
1 3 2

    验证二叉搜索树

    给定一个二叉树，判断其是否是一个有效的二叉搜索树。

    假设一个二叉搜索树具有如下特征：
    节点的左子树只包含小于当前节点的数。
    节点的右子树只包含大于当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。

    图片.png

    这个题可以使用递归，也可以使用非递归方法。

    递归

    具体程序如下：

    // 98 验证二叉搜索树,递归
bool isValidBST_helper(BiTree root,long l,long r){
    if(root == NULL){
        return true;
    }
    if(l >= stoi(root->val) || r <= stoi(root->val)){
        return false;
    }
    if(isValidBST_helper(root->left,l,stoi(root->val)) && isValidBST_helper(root->right,stoi(root->val),r)){
        return true;
    }
    return false;
}
bool isValidBST(BiTree root){
    return isValidBST_helper(root,LONG_MIN,LONG_MAX);
}

    测试程序：

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

    测试结果：

    2
1 3
# # # #
1

    5
1 4
# # 3 6
# # # #
0

    非递归

    具体程序如下：

    // 98 验证二叉搜索树,非递归
bool isValidBST_(BiTree root){
    stack<BiTree> sk;
    long temp = LONG_MIN;
    while(root || sk.size()){
        while(root){
            sk.push(root);
            root = root->left;
        }
        root = sk.top();
        sk.pop();
        if(temp >= stoi(root->val)){
            return false;
        }
        temp = stoi(root->val);
        root = root->right;
    }
    return true;
}

    测试程序：

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

    测试结果为：

    2
1 3
# # # #
1

    5
1 4
# # 3 6
# # # #
0

    二叉树的层次遍历

    给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

    图片.png

    二叉树的层次遍历在之前的博客中也是提到过的，这里我们再回顾一遍吧。
    关键点是用队列保存每一层节点，在本层节点数据域被保存后，用队列保存下一层节点，直到遍历完每一层。

    具体的程序如下：

    // 102 二叉树的层次遍历,由于本题的代码模板函数和原有的函数重复了,在原函数的基础上增加了下划线以区分
vector<vector<int>> levelOrder_(BiTree root){
    vector<vector<int>> res;
    queue<BiTree> q;
    if(root == NULL){
        return res;
    }
    q.push(root);
    while(!q.empty()){
        //， ，每一层的节点数
        int n = q.size();
        //用以存储该层节点的数据域
        vector<int> level;
        while(n--){
            //以此将本层的节点出队列
            BiTree node = q.front();
            q.pop();
            //存入level中
            level.push_back(stoi(node->val));
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
        //保存该层所有节点
        res.push_back(level);
    }
    return res;
}

    测试程序：

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

    测试结果为：

    3
9 20
# # 15 7
# # # #
3
9 20
15 7

    二叉树的锯齿形层次遍历

    给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

    图片.png

    这个题和上一题很相似，但是有所不同，若根节点算第一层的话，奇数层是从左到右记录的，偶数层是从右到左记录的。
    那么我们使用一个栈是不够的，需要有两个栈，一个从左到右记录，一个从右到左记录，先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。直到两个栈都为空了，遍历完成。

    具体程序如下：

    // 103 二叉树的锯齿形层次遍历
vector<vector<int>> zigzagLevelOrder(BiTree root){
    vector<vector<int>> res;
    if(root == NULL){
        return res;
    }
    //设置两个栈，一个从左到右记录，一个从右到左记录
    //即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行
    stack<BiTree> left_stack,right_stack;
    //奇数层，从左到右记录,记录完后将该层所有节点的左，右子节点压入右栈
    //偶数层，从右到左记录,记录完后将该层所有节点的右，左子节点压入左栈
    left_stack.push(root);
    while(left_stack.size() != 0 || right_stack.size() != 0){
        if(left_stack.size() != 0){
            res.push_back(vector<int> ());
            while(left_stack.size() != 0){
                //得到当前节点
                BiTree node = left_stack.top();
                left_stack.pop();
                res.back().push_back(stoi(node->val));
                //左节点压入右栈
                if(node->left){
                    right_stack.push(node->left);
                }
                //右节点压入右栈
                if(node->right){
                    right_stack.push(node->right);
                }
            }
        }
        if(right_stack.size() != 0){
            res.push_back(vector<int> ());
            while(right_stack.size() != 0){
                //得到当前节点
                BiTree node = right_stack.top();
                right_stack.pop();
                res.back().push_back(stoi(node->val));
                //右节点压入左栈
                if(node->right){
                    left_stack.push(node->right);
                }
                //左节点压入左栈
                if(node->right){
                    left_stack.push(node->left);
                }
            }
        }
    }
    return res;
}

    测试程序如下：

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

    测试结果如下：

    3
9 20
# # 15 7
# # # #
3
20 9
15 7

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

    相关文章

      网友评论

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

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

        延伸阅读

        深度阅读

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

        栏目导航

        热点阅读

        刷题总结

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

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

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

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

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

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