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

二叉树 LeetCode 刷题小结(三)

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

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

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

路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

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

图片.png 图片.png

当一个节点为空时，直接返回；当其左右节点均为空时，满足叶子节点条件，每经过 1 个节点，在路径和上减去该节点 val 值，当 sum 为 0 时，满足左右子树为空，sum 为 0 时，将 path 添加到 res，否则进行回溯。path 弹出之前添加的值，恢复 sum。

具体程序如下：

// 113 路径总和 II
void pathSum_helper(BiTree root,vector<vector<int>> &res,vector<int> &path,int sum){
    if(root == NULL){
        return ;
    }
    path.push_back(stoi(root->val));
    sum -= stoi(root->val);
    if((root->left == NULL) && (root->right == NULL) && sum == 0){
        //满足条件，左右子树为空，和为sum，path入res
        res.push_back(path);
    }
    //递归左子树
    pathSum_helper(root->left,res,path,sum);
    //递归左子树
    pathSum_helper(root->right,res,path,sum);
    //将path最后一个元素去除
    path.pop_back();
    sum += stoi(root->val);
}
vector<vector<int>> pathSum(BiTree root,int sum){
    /*
    将 path,res 设置成全局变量或者类成员变量更优
    这里为了避免变量命名冲突,设置成局部变量
    */
    vector<int> path;
    vector<vector<int>> res;
    pathSum_helper(root,res,path,sum);
    return res;
}

测试程序：

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

测试结果为：

5
4 8
11 # 13 4
7 2 # # 5 1
# # # # # # # #
22
5 4 11 2
5 8 4 5

求根到叶子节点数字之和

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

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

图片.png

程序如下：

// 129 求根到叶子节点数字之和
void sumNumbers_helper(BiTree root,int path,int &sum){
    if(root == NULL){
        return ;
    }
    path = path*10 + stoi(root->val);
    if(root->left == NULL && root->right == NULL){
        sum += path;
    }else{
        sumNumbers_helper(root->left,path,sum);
        sumNumbers_helper(root->right,path,sum);
    }
    path = path/10;
}
int sumNumbers(BiTree root){
    int sum = 0;
    sumNumbers_helper(root,0,sum);
    return sum;
}

测试程序：

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

结果为：

1
2 3
# # # #
25

4
9 0
5 1 # #
# # # #
1026

完全二叉树的节点个数

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 (1,2^{h})\ 个节点。

图片.png

先给出一种简洁的做法：

// 222 完全二叉树的节点个数
int countNodes_(BiTree root){
    return (root == NULL) ? 0 : (1 + countNodes_(root->left) + countNodes_(root->right));
}

测试程序：

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

测试结果：

1
2 3
4 5 6 #
# # # # # #
6

另一种解法：

// 222 完全二叉树的节点个数
int countNodes_helper(BiTree root){
    int depth = 0;
    while(root){
        depth++;
        root = root->left;
    }
    return depth;
}
int countNodes(BiTree root){
    int depth = countNodes_helper(root);
    int ans = (1<<depth) - 1;
    for(int i=1;i<depth;i++){
        if(countNodes_helper(root->right) + i == depth){
            root = root->right;
        }else{
            root = root->left;
            ans -= 1<<(depth - i - 1);
        }
    }
    return ans;
}

测试程序：

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

测试结果：

1
2 3
4 5 6 #
# # # # # #
6

二叉搜索树中第 k 小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

图片.png

二叉搜索树的结果可知，在一个节点中(左右子树都存在)，那么左子树的值最小，其次该节点，最后右子树，我们可以使用中序遍历的方式，因为中序遍历得到的是一个升序序列。
具体程序如下：

// 230 二叉搜索树中第 k 小的元素
void kthSmallest_helper(BiTree root,int k,int &index,int &ans){
    if(!root){
        return ;
    }
    kthSmallest_helper(root->left,k,index,ans);
    index++;
    if(index == k){
        ans = stoi(root->val);
    }
    kthSmallest_helper(root->right,k,index,ans);
}
int kthSmallest(BiTree root,int k){
    //递归
    int index = 0;
    int ans = 0;
    kthSmallest_helper(root,k,index,ans);
    return ans;
}

测试程序：

int main(){
    //test
    //cout<<"test:......"<<endl;
    BiTree tree = levelCreate();
    int k;
    cin>>k;
    cout<<kthSmallest(tree,k)<<endl;
    return 0;
}

测试结果：

3
1 4
# 2 # #
# #
1
1

5
3 6
2 4 # #
1 # # #
# #
3
3

把二叉搜索树转换为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

图片.png

若只考虑一个两层的二叉树，如同样例中的树，其右子树不需要动，根节点加上右子树的值，然后左子树加上根节点的值，所以我们需要反中序遍历，同时考虑到累加性，得保存每次增加的值 sum。
具体的程序如下：

// 538 把二叉搜索树转换为累加树
void convertBST_helper(BiTree root,int &sum){
    if(root != NULL){
        convertBST_helper(root->right,sum);
        sum += stoi(root->val);
        root->val = to_string(sum);
        convertBST_helper(root->left,sum);
    }
}
BiTree convertBST(BiTree root){
    int sum = 0;
    convertBST_helper(root,sum);
    return root;
}

测试程序：

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

测试结果为：

5
2 13
# # # #
18 20 13

二叉树的坡度

给定一个二叉树，计算整个树的坡度。

一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。

整个树的坡度就是其所有节点的坡度之和。

图片.png

程序如下：

// 563 二叉树的坡度
int findTilt_helper(BiTree root,int &sum){
    if(root == NULL){
        return 0;
    }
    int l = findTilt_helper(root->left,sum);
    int r = findTilt_helper(root->right,sum);
    sum += abs(l - r);
    return l + r + stoi(root->val);
}
int findTilt(BiTree root){
    int sum = 0;
    findTilt_helper(root,sum);
    return sum;
}

测试程序：

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

测试结果：

1
2 3
# # # #
1

二叉搜索树的最小绝对差

给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

图片.png

注意: 树中至少有2个节点。

我们知道中序遍历二叉搜索树，可以得到一个升序序列，那么最小绝对差自然在序列中的两个相邻节点之间。
具体程序如下：

// 530 二叉搜索树的最小绝对差
void getMinimumDifference_helper(BiTree root,int &pre,int &curr){
    if(root == NULL){
        return ;
    }
    getMinimumDifference_helper(root->left,pre,curr);
    if(pre >= 0){
        curr = min(curr,stoi(root->val) - pre);
    }
    pre = stoi(root->val);
    getMinimumDifference_helper(root->right,pre,curr);
}
int getMinimumDifference(BiTree root){
    int pre = INT_MIN;
    int curr = INT_MAX;
    getMinimumDifference_helper(root,pre,curr);
    return curr;
}

测序程序：

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

测试结果：

1
# 3
2 #
# #
1

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

相关文章

网友评论

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

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

    延伸阅读

    深度阅读

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

    栏目导航

    热点阅读

    刷题总结

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

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

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

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

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

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