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

数据结构与算法再探(三)树

目录

二叉树

二叉树遍历

C++ 递归

C++迭代

 python递归

层次遍历

二叉树的最大深度及直径

python 版递归树深度

递归求宽度

反转二叉树

python递归实现

 代码可视化


二叉树

二叉树遍历

C++ 递归

通过调用自身来解决问题,将原问题分解为一个或多个规模较小的相似子问题,在函数体内调用自身来解决问题。递归算法需要定义基本情况(边界条件),以防止无限递归。

class Solution {
public:
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val); #先根
        preorder(root->left, res);
        // res.push_back(root->val); #中
        preorder(root->right, res);
        //res.push_back(root->val); #后
    }
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

C++迭代

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        stack<TreeNode*> stk;
        stk.push(root);
        while (stk.size()) {
            auto node = stk.top();
            stk.pop();
            res.push_back(node->val);
            if (node->right) {
                stk.push(node->right);
            }
            if (node->left) {
                stk.push(node->left);
            }
        }
        return res;
    }
};

 python递归

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if not root:
                return
            res.append(root.val) #改变位置进行先、中、后、遍历
            dfs(root.left)
            dfs(root.right)
        res=[]
        dfs(root)
        return res

层次遍历

637. 二叉树的层平均值 - 力扣(LeetCode)

vector<double> averageOfLevels(TreeNode* root) {
    vector<double> ans;
    if(!root){
        return ans;
    }
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        int count=q.size();
        double sum=0;
        for(int i=0;i<count;++i){
            TreeNode* node=q.front();
            q.pop();
            sum+=node->val;
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
        ans.push_back(sum/count);
    }
    return ans;
}

二叉树的最大深度及直径

python 版递归树深度

递归虽然简洁但是有时难以写出和理解,每一次的递归调用都是一次完成函数的调用,需要梳理在递归临界点返,和返回后函数继续执行后最后,还要梳理回到上一次的递归调用节点间继续调用,着实难以理解,但是递归很多适用于树的操作。

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        ld=self.maxDepth(root.left)
        rd=self.maxDepth(root.right)
        return max(ld,rd)+1
#递归子问题返回结果给上一级,不能陷入直观上的顺序执行,return max(ld,rd)+1却决于左右子树是否
#有节点,这个返回值第一次返回时也许经历了很多次的函数压栈,多次调用

递归求宽度

543. 二叉树的直径

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.res=0
        def dfs(root):
            if not root: return 0
            ld=dfs(root.left)
            rd=dfs(root.right)
            self.res=max(self.res,ld+rd)
            return max(ld,rd)+1
        dfs(root)
        return self.res

反转二叉树

翻转二叉树

python递归实现

class Solution:
    def flipTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:return
        temp=root.left
        root.left, root.right=self.flipTree(root.right),self.flipTree(temp)
        return root

 代码可视化

通过可视化发现为什么临时变量保存左节点,以及临时变量在递归中的变化

 代码可视化
 


http://www.kler.cn/a/447856.html

相关文章:

  • 成方金融科技后端部分笔试题 - 解析
  • 摩尔信使MThings的逻辑控制功能范例
  • python coding(二) Pandas 、PIL、cv2
  • clickhouse优化记录
  • SQL 插入数据详解
  • LabVIEW深海气密采水器测控系统
  • 本地电脑使用命令行上传文件至远程服务器
  • Pydantic 2.0 完整指南
  • k8s 创建密钥以及证书安装
  • Jackson 的@JsonRawValue
  • Python 自带的日期日历处理大师:calendar 库
  • Paimon 是什么?Apache Paimon简介
  • 项目2路由交换
  • 米思齐图形化编程之ESP32开发指导
  • PostgreSQL表达式的类型
  • 晶闸管-直流电动机调速系统设计【MATLAB源码+Word文档】
  • 【系统移植】NFS服务器环境搭建——挂载根文件系统
  • Linux网络——网络套接字
  • java小知识点:比较器
  • 使用PyTorch实现GPT-2直接偏好优化训练:DPO方法改进及其与监督微调的效果对比
  • 机器学习(四)-回归模型评估指标
  • 【LeetCode】906、超级回文数
  • vue入门教程:组件透传 Attributes
  • c++领域展开第四幕——类和对象(上篇收尾 this指针、c++和c语言的初步对比)超详细!!!!
  • 如何使用PSQL Tool还原pg数据库(sql格式)
  • Kubernetes网络管理