当前位置：首页 > article >正文

初级数据结构——二叉树题库（c++）

article 2024/12/2 1:19:57

这里写目录标题

前言
[1.——965. 单值二叉树](https://leetcode.cn/problems/univalued-binary-tree/)
[2.——222. 完全二叉树的节点个数](https://leetcode.cn/problems/count-complete-tree-nodes/)
[3.——144. 二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/)
[4.——94. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/description/)
[5.——145. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/description/)
[6.——226. 翻转二叉树](https://leetcode.cn/problems/invert-binary-tree/description/)
[7.——1022. 从根到叶的二进制数之和](https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/)
[8.——1379. 找出克隆二叉树中的相同节点](https://leetcode.cn/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/description/)
[9.——1302. 层数最深叶子节点的和](https://leetcode.cn/problems/deepest-leaves-sum/description/)
[10.——654. 最大二叉树](https://leetcode.cn/problems/maximum-binary-tree/description/)
结语

前言

在上期（蓝色字体可以点进去）我们一起学习了初级数据结构——二叉树，那么这期我们来运用二叉树思想进行实战，巩固知识点。

在这里插入图片描述

1.——965. 单值二叉树

（蓝色字体可以点进去看原题）

代码题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if(root==NULL)return true;
        if(root->left){//从根节点的左子结点递归遍历完
            if(root->val!=root->left->val)return false;
            if(!isUnivalTree(root->left))return false;
        }
        if(root->right){//再从根节点的右子节点递归遍历完
            if(root->val!=root->right->val)return false;
            if(!isUnivalTree(root->right))return false;
        }
        return true;
    }
};

2.——222. 完全二叉树的节点个数

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==NULL)return 0;
        int rc=countNodes(root->right);//左子树节点个数
        int lc=countNodes(root->left);//右子树节点个数
        return lc+rc+1;
    }
};

3.——144. 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    vector<int> ret;
    void preorder(TreeNode* root){
        if(root){
            ret.push_back(root->val);
            preorder(root->left);
            preorder(root->right);
        }
        
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        ret.clear();
        preorder(root);
        return ret;
    }
};

4.——94. 二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    vector<int>ret;
    void inorder(TreeNode* root){
        if(root){
            inorder(root->left);
            ret.push_back(root->val);
            inorder(root->right);
        }
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        ret.clear();
        inorder(root);
        return  ret;
    }
};

5.——145. 二叉树的后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    vector<int>ret;
    void postOrder(TreeNode* root){
        if(root){
            postOrder(root->left);
            postOrder(root->right);
            ret.push_back(root->val);
        }
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        ret.clear();
        postOrder(root);
        return ret;
    }
};

6.——226. 翻转二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)return NULL;
        TreeNode* l=invertTree(root->left);//递归反转左子树
        TreeNode* r=invertTree(root->right);//递归反转右子树
        root->left=r;//将root的左子树变为右子树
        root->right=l;//将root的右子树变为左子树
        return root;
    }
};

7.——1022. 从根到叶的二进制数之和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    int sum;
    void sumRoot(TreeNode* root,int pre){
        if(!root->left&&!root->right){//如果是叶子结点就从该叶子结点进行求和
            sum+=pre*2+root->val;
        }
        if(root->left){//如果该节点左子结点不为空就继续访问
            sumRoot(root->left,pre*2+root->val);
        }
        if(root->right){//与上面同理
            sumRoot(root->right,pre*2+root->val);
        }
    }
public:
    int sumRootToLeaf(TreeNode* root) {
        sum=0;
        sumRoot(root,0);
        return sum;
    }
};

8.——1379. 找出克隆二叉树中的相同节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target){
        if(original==target)return cloned;
        if(original->left){
            TreeNode*t=getTargetCopy(original->left,cloned->left,target);//两颗二叉树都相同递归调用
            if(t)return t;
        }
        if(original->right){
            TreeNode*t=getTargetCopy(original->right,cloned->right,target);
            if(t)return t;
        }
        return NULL;//如果做右子树都为空，上面已经判断如果original与cloned不同所以直接返回空
    }
};

9.——1302. 层数最深叶子节点的和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    int maxDepth;//记录最大深度
    void getMaxDepth(TreeNode* root,int depth){
        if(root==NULL)return;//递归出口
        if(depth>maxDepth)maxDepth=depth;
        getMaxDepth(root->left,depth+1);
        getMaxDepth(root->right,depth+1);
    }
    int sumDepthValue(TreeNode* root,int depth){
        if(root==NULL)return 0;
        if(depth==maxDepth)return root->val;//如果当前深度等于最大深度就累加结果
        return sumDepthValue(root->left,depth+1)+sumDepthValue(root->right,depth+1);
        //左子树加上右子树最大深度的和
    }

public:
    int deepestLeavesSum(TreeNode* root) {
        getMaxDepth(root,0);
        return sumDepthValue(root,0);
    }
};

10.——654. 最大二叉树

这一题不太理解的这一看我这期文章

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    TreeNode* dfs(vector<int>& nums,int l,int r){//其实这整个过程就是构造大顶堆的过程
        if(l>r)return NULL;//递归出口，递归到当l>r是说明这是一个空数
        int maxId=l;
        for(int i=l+1;i<=r;i++){//找二叉树中最大值的下标
            if(nums[i]>nums[maxId])maxId=i;
        }
        TreeNode*root=new TreeNode();//定义一个新节点，递归构造它的左右子节点
        root->left=dfs(nums,l,maxId-1);
        root->right=dfs(nums,maxId+1,r);
        root->val=nums[maxId];//将root的值设为最大值
        return root;
    }   
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return dfs(nums,0,nums.size()-1);
    }
};