【数据结构刷题专题】—— 二叉树

这篇具有很好参考价值的文章主要介绍了【数据结构刷题专题】—— 二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉树

二叉树刷题框架
【数据结构刷题专题】—— 二叉树,力扣刷题,数据结构,二叉树,c++
二叉树的定义:

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL);
};

1 二叉树的遍历方式

【1】前序遍历

class Solution {
public:
    void traversal(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        vec.push_back(node->val);
        traversal(node->left, vec);
        traversal(node->right, vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

【2】后序遍历

class Solution {
public:
    void traversal(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        traversal(node->left, vec);
        traversal(node->right, vec);
        vec.push_back(node->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

【3】中序遍历

class Solution {
public:
    void traversal(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        traversal(node->left, vec);
        vec.push_back(node->val);
        traversal(node->right, vec);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

【4】层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            vector<int> vec;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

2 二叉树的属性

【1】101. 对称二叉树

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        if (left != NULL && right == NULL) return false;
        else if (left == NULL && right != NULL) return false;
        else if (left == NULL && right == NULL) return true;
        else if (left->val != right->val) return false;
        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        return outside && inside;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

【2】104. 二叉树的最大深度
迭代法:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            depth++;
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return depth;
    }
};

递归法:

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int left = getDepth(node->left);
        int right = getDepth(node->right);
        return 1 + max(left, right);
    }
    int maxDepth(TreeNode* root) {
        return getDepth(root);
    }
};

【3】111.二叉树的最小深度
递归法:

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int left = getDepth(node->left);
        int right = getDepth(node->right);
        if (node->left != NULL && node->right == NULL) return 1 + left;
        if (node->left == NULL && node->right != NULL) return 1 + right;
        return 1 + min(left, right);
    }
    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

迭代法:

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (root == NULL) return 0;
        que.push(root);
        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            depth++;
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (node->left == NULL && node->right == NULL) return depth;
            }
        }
        return depth;
    }
};

【4】222. 完全二叉树的节点个数
递归法:

class Solution {
public:
    int getNum(TreeNode* node) {
        if (node == NULL) return 0;
        int left = getNum(node->left);
        int right = getNum(node->right);
        return 1 + left + right;
    }
    int countNodes(TreeNode* root) {
        return getNum(root);
    }
};

迭代法:

class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        if (root == NULL) return 0;
        que.push(root);
        int num = 0;
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                num++;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return num;
    }
};

【5】110. 平衡二叉树

class Solution {
public:
    int getHeight(TreeNode* node) {
        if (node == NULL) return 0;
        int left = getHeight(node->left);
        if (left == -1) return -1;
        int right = getHeight(node->right);
        if (right == -1) return -1;
        return abs(left - right) > 1 ? -1 : 1 + max(left, right);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

【6】257. 二叉树的所有路径

class Solution {
public:
    void traversal(TreeNode* node, string path, vector<string>& result) {
        path += to_string(node->val);
        if (node->left == NULL && node->right == NULL) {
            result.push_back(path);
            return;
        }
        if (node->left) traversal(node->left, path + "->", result);
        if (node->right) traversal(node->right, path + "->", result);
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

【7】404. 左叶子之和

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int left = sumOfLeftLeaves(root->left);
        if (root->left && root->left->left == NULL && root->left->right == NULL) {
            left = root->left->val;
        }
        int right = sumOfLeftLeaves(root->right);
        return left + right;
    }
};

【8】513. 找树左下角的值
迭代法:

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root);
        int val = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == 0) val = node->val;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return val;
    }
};

【9】112. 路径总和

class Solution {
public:
    bool pathSum(TreeNode* node, int count) {
        if (node->left == NULL && node->right == NULL && count == 0) return true;
        if (node->left == NULL && node->right == NULL) return false;
        if (node->left) {
            count -= node->left->val;
            if (pathSum(node->left, count)) return true;
            count += node->left->val;
        }
        if (node->right) {
            count -= node->right->val;
            if (pathSum(node->right, count)) return true;
            count += node->right->val;
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        return pathSum(root, targetSum - root->val);
    }
};

【10】543. 二叉树的直径

class Solution {
public:
    int ans;
    int Depth(TreeNode* node) {
        if (node == NULL) return 0;
        int left = Depth(node->left);
        int right = Depth(node->right);
        ans = max(ans, 1 + left + right);
        return 1 + max(left, right);
    }
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        Depth(root);
        return ans - 1;
    }
};

【11】124. 二叉树中的最大路径和

class Solution {
public:
    int ans = INT_MIN;
    int dfs(TreeNode* node) {
        if (node == NULL) return 0;
        ans = max(ans, node->val);
        int lSum = dfs(node->left);
        int rSum = dfs(node->right);
        lSum = max(0, lSum); rSum = max(0, rSum);
        ans = max(ans, node->val + lSum + rSum);
        return max(node->val + lSum, node->val + rSum);
    }
    int maxPathSum(TreeNode* root) {
        ans = max(ans, dfs(root));
        return ans;
    }
};

3 二叉树的修改和构造

【1】226. 翻转二叉树

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);
        if (root->left) invertTree(root->left);
        if (root->right) invertTree(root->right);
        return root;
    }
};

【2】106. 从中序与后序遍历序列构造二叉树

class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        if (postorder.size() == 1) return root;
        int qiege;
        for (qiege = 0; qiege <= inorder.size(); qiege++) {
            if (inorder[qiege] == root->val) break;
        }
        vector<int> leftInorder(inorder.begin(), inorder.begin() + qiege);
        vector<int> rightInorder(inorder.begin() + qiege + 1, inorder.end());
        postorder.resize(postorder.size() - 1);
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

【3】654. 最大二叉树
构造树一般采用的是前序遍历

class Solution {
public:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left >= right) return NULL;
        int index = left;
        for (int i = left + 1; i < right; i++) {
            if (nums[i] > nums[index]) index = i;
        }
        TreeNode* root = new TreeNode(nums[index]);
        root->left = traversal(nums, left, index);
        root->right = traversal(nums, index + 1, right);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};

【4】617. 合并二叉树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL) return root2;
        if (root2 == NULL) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

【5】114. 二叉树展开为链表

class Solution {
public:
    void traversal(TreeNode* node) {
        if (node == NULL) return;
        traversal(node->left);
        traversal(node->right);
        TreeNode* left = node->left;
        TreeNode* right = node->right;
        node->left = NULL;
        node->right = left;
        while (node->right) node = node->right;
        node->right = right;
        return;
    }
    void flatten(TreeNode* root) {
        traversal(root);
        return;
    }
};

4 求二叉树的属性

【1】700. 二叉搜索树中的搜索

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != NULL) {
            if (root->val > val) {
                root = root->left;
            } else if (root->val < val) {
                root = root->right;
            } else return root;
        }
        return root;
    }
};

【2】98. 验证二叉搜索树

class Solution {
public:
    long long maxVel = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);
        if (root->val > maxVel) maxVel = root->val;
        else return false;
        bool right = isValidBST(root->right);
        return left && right;
    }
};

【3】530. 二叉搜索树的最小绝对差
遇到在二叉搜索树上求什么最值啊,差值之类的,就把它想成在一个有序数组上求最值,求差值
把二叉搜索树转换成有序数组,然后遍历一遍数组,就统计出来最小差值

class Solution {
public:
    vector<int> vec;
    int ans = INT_MAX;
    void traversal(TreeNode* node) {
        if (node == NULL) return;
        traversal(node->left);
        vec.push_back(node->val);
        traversal(node->right);
    }
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            ans = min(ans, vec[i] - vec[i - 1]);
        }
        return ans;
    }
};

在递归中记录前一个节点的指针

class Solution {
public:
    int result = INT_MAX;
    TreeNode* pre = NULL;
    void traversal(TreeNode* node) {
        if (node == NULL) return;
        traversal(node->left);
        if (pre != NULL) result = min(result, node->val - pre->val);
        pre = node;
        traversal(node->right);
    }
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

【4】501. 二叉搜索树中的众数

class Solution {
public:
    void traversal(TreeNode* cur, unordered_map<int, int>& map) {
        if (cur == NULL) return;
        map[cur->val]++;
        traversal(cur->left, map);
        traversal(cur->right, map);
        return;
    }
    static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    }
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map;
        vector<int> result;
        if (root == NULL) return result;
        traversal(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp);
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            if (vec[0].second == vec[i].second) result.push_back(vec[i].first);
            else break;
        }
        return result;
    }
};

【5】把二叉搜索树转换为累加树

class Solution {
public:
    int pre = 0;
    void traversal(TreeNode* node) {
        if (node == NULL) return;
        traversal(node->right);
        node->val += pre;
        pre = node->val;
        traversal(node->left);

    }
    TreeNode* convertBST(TreeNode* root) {
        if (root == NULL) return root;
        traversal(root);
        return root;
    }
};

【6】230. 二叉搜索树中第K小的元素

class Solution {
public:
    int maxVel = INT_MIN;
    vector<int> vec;
    void traversal(TreeNode* node) {
        if (node == NULL) return;
        traversal(node->left);
        if (node->val > maxVel) {
            vec.push_back(node->val);
            maxVel = node->val;
        }
        traversal(node->right);
        return;
    }
    int kthSmallest(TreeNode* root, int k) {
        traversal(root);
        return vec[k - 1];
    }
};

【7】二叉树的右视图

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if (root == NULL) return result;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == (size - 1)) result.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

5 二叉树的公共祖先问题

【1】236. 二叉树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q || root == NULL) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != NULL && right != NULL) return root;
        if (left != NULL && right == NULL) return left;
        else if (left == NULL && right != NULL) return right;
        else return NULL;
    }
};

【2】235. 二叉搜索树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root) {
            if (root->val > q->val && root->val > p->val) root = root->left;
            else if (root->val < q->val && root->val < p->val) root = root->right;
            else return root;
        }
        return NULL;
    }
};

6 二叉搜索树的修改和构造

【1】二叉搜索树的插入操作

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if (root->val > val) root->left = insertIntoBST(root->left, val);
        if (root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

【2】450. 删除二叉搜索树中的节点

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == NULL) return root;
        if (root->val == key) {
            if (root->left == NULL && root->right == NULL) {
                delete root;
                return NULL;
            } else if (root->left == NULL) {
                auto tmp = root->right;
                delete root;
                return tmp;
            } else if (root->right == NULL) {
                auto tmp = root->left;
                delete root;
                return tmp;
            } else {
                TreeNode* cur = root->right;
                while (cur->left != NULL) {
                    cur = cur->left;
                }
                cur->left = root->left;
                TreeNode* tmp = root;
                root = root->right;
                delete tmp;
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

【3】669. 修剪二叉搜索树

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == NULL) return root;
        if (root->val < low) return trimBST(root->right, low, high);
        if (root->val > high) return trimBST(root->left, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

【4】108. 将有序数组转换为二叉搜索树

class Solution {
public:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traversal(nums, 0, nums.size() - 1);
    }
};

二叉树刷题专题到此结束,读者对题目有更好的解答欢迎讨论。文章来源地址https://www.toymoban.com/news/detail-845970.html

到了这里,关于【数据结构刷题专题】—— 二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】力扣:二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例1: 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2: 输入:root = [1] 输出:[[1]] 示例 3: 输入:root = [] 输出:[] 来源:力扣(LeetCode) 链接:https://leetcode.cn/p

    2024年02月13日
    浏览(47)
  • DSt:数据结构的最强学习路线之数据结构知识讲解与刷题平台、刷题集合、问题为导向的十大类刷题算法(数组和字符串、栈和队列、二叉树、堆实现、图、哈希表、排序和搜索、动态规划/回溯法/递归/贪心/分治)总

    Algorithm:【算法进阶之路】之算法面试刷题集合—数据结构知识和算法刷题及其平台、问题为导向的十大类刷题算法(数组和字符串、链表、栈和队列、二叉树、堆、图、哈希表、排序和搜索、回溯算法、枚举/递归/分治/动态规划/贪心算法)总结 目录 相关文章

    2024年02月08日
    浏览(56)
  • 力扣刷题-二叉树-合并二叉树

    合并二叉树是操作两棵树的题目里面很经典的,如何对两棵树遍历以及处理? 给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为

    2024年01月17日
    浏览(46)
  • 数据结构:力扣刷题

      给你一个  升序排列  的数组  nums  ,请你  原地  删除重复出现的元素,使每个元素  只出现一次  ,返回删除后数组的新长度。元素的  相对顺序  应该保持  一致  。然后返回  nums  中唯一元素的个数。 考虑  nums  的唯一元素的数量为  k  ,你需要做以下事情确

    2024年02月13日
    浏览(44)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(48)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(58)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(63)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(47)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(56)
  • 数据结构-二叉树-二叉树左右孩子交换(递归)

     注:本文采用队列和递归的算法进行创建和层次遍历。同时不能采用BFS和DFS,因为需要把当前根节点的左孩、右孩勾链并输入才能递归下一个根节点; 队列用于存储此时应该递归的根节点; 格式:每一行尾不能有空格; Description 根据输入利用二叉链表创建二叉树,并将所

    2024年02月04日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包