二叉树 LeetCode 刷题小结(一)

本节我们将汇总一些 LeetCode 有关二叉树的题。

鉴于 LeetCode 测试的方式是系统给出样例并自动测试的。
我们在本地的话，可以手动输入样例，返回测试结果。
首先我们建立二叉树的节点。为了能手动输入数据，我们使用层序遍历的方式创建树，使用层序遍历查看树是否满足要求，之后的工作和 LeetCode 就类似了。

所有代码的地址位于 github 上，后续将持续更新。

基本的程序框架

只要能手动输入树的信息并保存下来即可，这里我们使用了层序遍历的方式创建树。为了更好理解，我们使用层序遍历的方式查看树。
代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef string ElemType;
//定义树的节点
typedef struct BinaryNode{
    //节点
    ElemType val;
    //左子树
    BinaryNode* left;
    //右子树
    BinaryNode* right;
    BinaryNode(ElemType x) : val(x),left(NULL),right(NULL){}
}BinaryNode,*BiTree;

//二叉树
//层序遍历创建二叉树
/*
先将根节点入队，当队列不为空时，循环执行以下操作：
输入左子树的值，不为空，将其入队
输入右子树的值，不为空，将其入队
*/
BiTree levelCreate(){
    ElemType value;
    BiTree root;
    queue<BiTree> q;
    cin>>value;
    if(value == "#"){
        return NULL;
    }else{
        root = new BinaryNode(value);
        q.push(root);
    }
    while(!q.empty()){
        BiTree p = q.front();
        q.pop();
        cin>>value;
        if(value == "#"){
            p->left = NULL;
        }else{
            p->left = new BinaryNode(value);
            q.push(p->left);
        }
        cin>>value;
        if(value == "#"){
            p->right = NULL;
        }else{
            p->right = new BinaryNode(value);
            q.push(p->right);
        }
    }
    return root;
}

//实现层次遍历
void levelOrder(BiTree root){
    queue<BiTree> q;
    q.push(root);
    while(!q.empty()){
        //每层的节点
        int num_level = q.size();
        while(num_level--){
            BiTree node = q.front();
            q.pop();
            cout<<node->val<<" ";
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
    }
}

// 摧毁树
void destroy(BiTree root){
    if(root != NULL){
        destroy(root->left);
        destroy(root->right);
        free(root);
    }
}

测试代码：

int main(){
    BiTree tree;
    /* 层序遍历
    1 2 3 4 5 6 7 # # # # # # # #
    */
    tree = levelCreate();
    levelOrder(tree);
    return 0;
}

测试一下：

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

正确。

接下来看一些例题，所有题均来自于leetcode，我们在这个框架的基础进行解题。方法不唯一。

相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

图片.png

这个题比较简单，如果两个节点为空，返回 true；在两个节点都不为空的情况下，数据域相同，说明该节点相同，继续递归其左子树后右子树；除此之外，均为 false。
程序如下：

// 100 相同的树
bool isSameTree(BiTree tree1,BiTree tree2){
    if(tree1 == NULL && tree2 == NULL){
        return true;
    }
    if(tree1 != NULL && tree2 != NULL && tree1->val == tree2->val){
        return isSameTree(tree1->left,tree2->left) && isSameTree(tree1->right,tree2->right);
    }else{
        return false;
    }
}

测试代码：

int main(){
    BiTree tree1 = levelCreate();
    BiTree tree2 = levelCreate();
    cout<<isSameTree(tree1,tree2)<<endl;
    return 0;
}

来测试一下

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

1 2 # # #
1 # 2 # #
0

1 2 1 # # # #
1 1 2 # # # #
0

下一题

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

图片.png

使用递归回溯的方式，比较左子树和右子树。
代码如下：

// 101 对称二叉树
bool isSymmetric_helper(BiTree tree_left,BiTree tree_right){
    if(tree_left == NULL && tree_right == NULL){
        return true;
    }
    if((tree_left == NULL || tree_right == NULL)||(tree_left->val != tree_right->val)){
        return false;
    }
    return isSymmetric_helper(tree_left->right,tree_right->left) && isSymmetric_helper(tree_left->left,tree_right->right);
}
bool isSymmetric(BiTree root){
    if(root == NULL){
        return true;
    }
    return isSymmetric_helper(root->left,root->right);
}

测试代码：

int main(){
    BiTree tree = levelCreate();
    cout<<isSymmetric(tree)<<endl;
    return 0;
}

测试一下：

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

1 2 2 # 3 # 3 # # # #
0

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

图片.png

节点为空时，返回 0 ；否则，递归的左子树，右子树，返回最大值并加一。
代码如下：

// 104 二叉树的最大深度
int maxDepth(BiTree root){
    if(root == NULL){
        return 0;
    }
    int left_ = maxDepth(root->left);
    int right_ = maxDepth(root->right);
    return max(left_,right_) + 1;
}

测试代码：

int main(){
    BiTree tree = levelCreate();
    cout<<maxDepth(tree)<<endl;
    return 0;
}

结果如下：

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

二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

图片.png

不同于层序遍历，此题需要递归。
代码如下：

// 107 二叉树的层次遍历 II
void levelOrderBottom_helper(vector<vector<ElemType>>& res,BiTree root,int level){
    if(root == NULL){
        return ;
    }
    if(level == res.size()){
        res.push_back({});
    }
    res[level].push_back(root->val);
    if(root->left){
        levelOrderBottom_helper(res,root->left,level+1);
    }
    if(root->right){
        levelOrderBottom_helper(res,root->right,level+1);
    }
}
vector<vector<ElemType>> levelOrderBottom(BiTree root){
    vector<vector<ElemType>> res;
    levelOrderBottom_helper(res,root,0);
    reverse(res.begin(),res.end());
    return res;
}

测试代码：

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

测试一下：

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

将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

图片.png

代码如下：

// 108 将有序数组转换为二叉搜索树
BiTree sortedArrayToBST_helper(vector<ElemType>& nums,int start_,int end_){
    if(start_ > end_){
        return nullptr;
    }
    int mid = start_ + (end_ - start_)/2;
    BiTree point = new BinaryNode(nums[mid]);
    point->left = sortedArrayToBST_helper(nums,start_,mid-1);
    point->right = sortedArrayToBST_helper(nums,mid+1,end_);
    return point;
}
BiTree sortedArrayToBST(vector<ElemType>& nums){
    if(nums.size() == 0){
        return nullptr;
    }
    return sortedArrayToBST_helper(nums,0,nums.size()-1);
}

测试代码：

int main(){
    vector<ElemType> nums{"-10","-3","0","5","9"};
    BiTree tree = sortedArrayToBST(nums);
    levelOrder(tree);
    return 0;
}

结果：

0 -10 5 -3 9

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

图片.png

代码如下：

// 110 平衡二叉树
int isBalanced_helper(BiTree root){
    if(root == NULL){
        return 1;
    }else{
        return max(isBalanced_helper(root->left),isBalanced_helper(root->right)) + 1;
    }
}
bool isBalanced(BiTree root){
    if(root == NULL){
        return true;
    }else{
        int ans = abs(isBalanced_helper(root->left) - isBalanced_helper(root->right));
        return (ans <= 1) && isBalanced(root->left) && isBalanced(root->right);
    }
}

测试代码：

int main(){
    BiTree tree = levelCreate();
    cout<<isBalanced(tree);
    return 0;
}

测试结果：

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

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

二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

图片.png

代码如下：

// 111 二叉树的最小深度
int minDepth(BiTree root){
    if(root == NULL){
        return 0;
    }
    int level = 1;
    if(root->left == NULL && root->right == NULL){
        return level;
    }
    if(root->left == NULL){
        return level + minDepth(root->right);
    }
    if(root->right == NULL){
        return level + minDepth(root->left);
    }
    return level + min(minDepth(root->left),minDepth(root->right));
}

测试代码：

int main(){
    BiTree tree = levelCreate();
    cout<<minDepth(tree);
    return 0;
}

测试结果：

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

路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

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

图片.png

代码如下：

// 112 路径总和
bool hasPathSum(BiTree root,int sum){
    if(root == NULL){
        return false;
    }
    if(root->left == NULL && root->right == NULL && sum == stoi(root->val)){
        return true;
    }
    if(root->left != NULL && hasPathSum(root->left,sum - stoi(root->val))){
        return true;
    }
    if(root->right != NULL && hasPathSum(root->right,sum - stoi(root->val))){
        return true;
    }
    return false;
}

测试代码：

int main(){
    BiTree tree = levelCreate();
    int sum;
    cin>>sum;
    cout<<hasPathSum(tree,sum)<<endl;
    return 0;
}

结果为：

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

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

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

友情链接更多精彩内容