首页 > 编程语言 >算法打卡 Day14（二叉树）-理论基础 + 递归遍历 + 迭代遍历 + 统一迭代

算法打卡 Day14（二叉树）-理论基础 + 递归遍历 + 迭代遍历 + 统一迭代

时间：2024-05-24 15:26:10浏览次数：16  
标签：node 遍历 迭代 st result push 二叉树

文章目录

理论基础

二叉树有满二叉树和完全二叉树两种主要的形式。

满二叉树

满二叉树是一种特殊的二叉树，其中每个节点要么是叶子节点（即没有子节点），要么恰好有两个子节点。

满二叉树的特性包括：

  1. 每一层的节点数是 2 的 n 次方，其中 n 是层数，从 0 开始。
  2. 一个满二叉树的节点总数为 2^(h+1) - 1，其中 h 是树的高度（根节点的高度为 0）。

在这里插入图片描述

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h 从 1 开始），则该层包含 1~ 2^(h-1) 个节点。

完全二叉树的特性包括：

  1. 除了最后一层外，其他所有层上的节点都是满的。
  2. 最后一层的节点从左到右尽可能填满，没有空位。

在这里插入图片描述

二叉搜索树

二叉搜索树是一个有序树，其特性为：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树

在这里插入图片描述

平衡二叉搜索树

平衡二叉搜索树是一种特殊的二叉搜索树，常见的平衡二叉树包括 AVL（Adelson-Velsky and Landis）树和红黑树，AVL 树的性质是一棵空树或它左右两个子树的高度差绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

C++ 中 map，set，multimap，multiset 的底层实现都是平衡二叉搜索树，所以 map 和 set 的增删操作时间复杂度是 l o g n logn logn

二叉树的存储方式

二叉树可以链式存储（指针），也可以顺序存储（数组）。

二叉树一般使用链式存储。

链式存储

在这里插入图片描述

顺序存储

在这里插入图片描述

如果父节点的数组下标是 i，左孩子是 i2+1，右孩子是 i2+2

二叉树的遍历方式

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。

前序、中序还是后续指的是中间节点的位置：

  • 前序遍历（递归法，迭代法）：中左右（5412678）
  • 中序遍历（递归法，迭代法）：左中右（1425768）
  • 后序遍历（递归法，迭代法）：左右中（1247865）

在这里插入图片描述

  1. 广度优先遍历：一层一层的去遍历。
  • 层次遍历（迭代法）

二叉树的定义

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

递归遍历

递归的三步分析：

  1. 确定递归函数的参数和返回值；
  2. 确定终止条件
  3. 确定单层递归的逻辑

leetcode 144-二叉树的前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

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

leetcode 145-二叉树的后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

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

leetcode 94-二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

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

迭代遍历

可以用栈模拟二叉树的遍历过程。

前序遍历

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

后序遍历

前序遍历的遍历顺序是“中左右”，我们可以在上面的代码的基础上稍微进行调整完成后序遍历的代码“左右中”，即先将左右的顺序调整变为“中右左”，然后在此基础上使用 reverse 函数翻转 result 数组变为“左右中”

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root == nullptr) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != nullptr) {
                st.pop();
                result.push_back(node->val);
                if (node->left) st.push(node->left);
                if (node->right) st.push(node->right);
            }
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

中序遍历

中序遍历和前后序遍历不同，前序遍历先访问的元素是中间节点，要处理的元素也是中间节点，访问和要处理的元素是一致的，而中序节点需要一层一层向下访问，直到到达树左边的最底部，然后才开始处理节点，处理顺序和访问顺序是不一致的。

使用迭代法完成中序遍历，需要借助指针的遍历来帮助访问节点，栈用于处理节点上的元素。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != nullptr || !st.empty()) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            }
            else {
                cur = st.top();
                st.pop();
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
        return result;
    }
};

统一迭代

前面我们用迭代法进行前中后序遍历时的方法没有统一，下面我们使用二叉树的同意迭代法进行解决：

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != nullptr) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != nullptr) {
                st.pop();
                if (node->right) st.push(node->right);
                st.push(node);
                st.push(nullptr);
                if (node->left) st.push(node->left);
            }
            else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

在此基础上我们只需要修改部分代码的位置就能实现前序遍历和后序遍历：

前序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != nullptr) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != nullptr) {
                st.pop();
                if (node->right) st.push(node->right);
                if (node->left) st.push(node->left);
                st.push(node);
                st.push(nullptr);
            }
            else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

后序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != nullptr) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != nullptr) {
                st.pop();
                st.push(node);
                st.push(nullptr);
                if (node->right) st.push(node->right);
                if (node->left) st.push(node->left);
            }
            else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

标签：node,遍历,迭代,st,result,push,二叉树
From： https://blog.csdn.net/Catherine121314/article/details/139167642

相关文章

  • c++ 迭代器
     c++迭代器，可以理解成指针的泛化。迭代器与指针：迭代器（Iterator）是指针（pointer）的泛化，提供了对对象的间接访问。迭代器针对容器，而指针类型针对数组。迭代器与模板：模板使得算法独立于存储的数据类型，即任何数据类型都可以使用该程序设计。而迭代器使得算法独立于使用的容器类型，即任......
  • 迭代器的一些简单理解
    迭代器的一些简单理解使用迭代器最方便的地方就是和算法库结合，对于实现只需要聚焦于算法，而不用过多考虑数据结构的实现。举一个常见的的例子，std::copy_n用作于范围元素的复制，适配于各个容器类型，并且演化出了back_inserter/front_inserter/inserter这类更上层的迭代器。//st......
  • 基于双向堆栈的二叉树双向迭代算法
    前言之前一直在研究avl树的迭代算法。我参考了C++标准库map的实现，发现他们在树节点上使用了parent指针+一个状态标志位的形式，去实现动态迭代。但是我不想用parent指针，因为觉得会增加调整指针的时间还有浪费存储空间。于是，在我的不屑努力下，终于，找到了一种基于堆栈实现的双向迭代......
  • 代码随想录算法训练营第第15天 | 层序遍历10道题 、226.翻转二叉树 、101. 对称二叉树
    层序遍历看完本篇可以一口气刷十道题，试一试，层序遍历并不难，大家可以很快刷了十道题。题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.二叉树的层序遍历.html层序遍历，10道题，一一通过，比较简单226.翻转二叉树（优先掌握递归）这道题目一些做过的同学理解的也不够深......
  • 广度优先搜索 洛谷P1443马的遍历（bfs超时问题）
    广度优先搜索洛谷P1443这里先介绍一下广度优先搜索：广度优先搜索就是先将第一步可能的步骤全部记录，遍历过后，再将由第一步到达的第二步全部记录并遍历，直到最后全部遍历。而此题要求我们求得最少步数，广度优先就能够达到最少步数的要求，因为广度优先是先通过搜索所有可能的第n步才......
  • 代码随想录算法训练营第十四天 | 二叉树遍历
    递归法文章讲解视频讲解递归三要素：1确定递归函数的参数和返回值2确定终止条件3确定单层递归的逻辑前序遍历题目链接递归的参数和返回值：传入当前节点和保存结果集的数组，不需要返回值终止条件：当前节点为空时单层递归逻辑：保存当前节点的值到结果集中classSolution......
  • 解锁产品迭代新速度：A/B测试在AI大模型时代的应用
      （DP微信公众号发布请标注原创，作者DataTester） 本文作者为火山引擎A/B测试平台DataTester的资深研发工程师刘明瑶。作为火山引擎数智平台VeDI旗下的核心产品，DataTester源于字节跳动长期的技术和业务沉淀，目前已经服务了数百家企业，助力企业在业务增长、用户转化、产品迭......
  • 代码随想录算法训练营第第14天 | 二叉树递归遍历（递归法、迭代、统一的迭代方法）
    递归遍历（必须掌握）二叉树的三种递归遍历掌握其规律后，其实很简单题目链接/文章讲解/视频讲解：https://programmercarl.com/二叉树的递归遍历.html迭代遍历（基础不好的录友，迭代法可以放过）题目链接/文章讲解/视频讲解：https://programmercarl.com/二叉树的迭代遍历.html统一迭代......
  • 迭代器、生成器
    迭代器【一】迭代器介绍迭代器就是用来迭代取值的工具，是重复反馈过程的程序目的是为了更加逼近我们想要的目标和结果每一次迭代得到的返回结果就是下一次迭代开始的初始值num_list=[1,2,3,4,5,6]count=0whilecount<len(num_list):#每一次使用的索引位置就是......
  • 关于 双向不循环列表的创建、插入、删除、遍历、检索、销毁
    双向循环链表公式双向不循环链表代码#include<stdio.h>#include<stdlib.h>#include<string.h>//宏定义一个数据域#defineDATA_LEN60//双向不循环链表的节点定义typedefstructdouble_link_list{//数据域chardata[DATA_LEN];//数据域，存......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99