二叉树之迭代法遍历
使用迭代法遍历二叉树 需要用到栈 题目不用看直接写思路 对于先序： 首先把跟结点放到栈里面 然后开始while，退出条件为栈不为空 把根节点对应的val放到数组result中， 然后把top给pop掉 if（）如果root->right不为空 push到栈中 if（）如果root->left不为空 push到栈中 循环结束后return一个result 注意这里是栈，所以我们先把righr放进入，然后再...
【Leetcode】二叉树基础题思路
🔥个人主页：Quitecoder 🔥专栏：Leetcode刷题 目录 1.单值二叉树2.相同的树3.对称二叉树4.另一棵树的子树 1.单值二叉树 单值二叉树是所有节点的值都相同的二叉树。实现这个检查的思路是通过递归方式遍历整棵树，并验证每个节点是否满足单值二叉树的条件 具体来说，递归函数 isUnivalTree 的工作流程如下： 基本情况: 如果当前节点 (root) 为空 (NULL)，那么根据单...
二叉树的广度优先遍历 - 华为OD统一考试(D卷)
题目描述 有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。 现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请输出层次遍历的结果。 输入描述 输入为两个字符串，分别是二叉树的后续遍历和中序遍历结果。 输出描述 输出二叉树的层次遍历结果。 示例1 输入：CBEFDA CBAEDF 输出：ABDCEF 说明：二叉树为： A / ...
代码随想录算法训练营第十四天 | 二叉树基础知识、递归遍历、迭代遍历、统一迭代
基础知识 递归遍历 解题思路 1.确定要传入的参数和返回值 2.注意终止条件 3.确定单层递归的逻辑 中序和后序按照中左右，左右中的顺序即可 class Solution {public: vector<int> preorderTraversal(TreeNode* root) { vector<int> result; traverSal(root,result); return result;...
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
题目描述 给定一个二叉树，找出其最大深度。 最大深度是从根节点到最远叶子节点的最长路径上的节点数。 示例: 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 最大深度是 3。 方法一：递归 解题步骤 如果节点为空，返回深度 0。递归计算左子树的最大深度。递归计算右子树的最大深度。返回左右子树深度的最大值加一（当前节点的深度）。 Python 示例 c...
数据结构面试常见问题：什么是二叉树？如何进行二叉树的遍历？
二叉树的介绍 二叉树是一种特殊的数据结构，它的每个元素都有零个、一个或两个子元素。这些元素被称为节点，每个节点都有一个值，以及两个指向其子节点的链接。 这种结构就像一个家族树，每个节点都有一个父节点（除了顶部的根节点），以及左右两个子节点。在实际项目中，我们经常会用到二叉树这种数据结构，它在数据存储、搜索等方面都有着广泛的应用。 接下来，我们将深入探讨二叉树的结构，包括节点、父节点、子节点、叶节点、根...
学习笔记-数据结构-树与二叉树（2024-4-22）
递归遍历二叉树 先序遍历： typedef struct BiTNode{ Elemtype data; struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;void PreOrder(BiTree T){ if(T!=NULL) { vist(T);//访问根节点 PreOrder(T->lchild);//递归遍历左子树 PreOrder(T->...
【leetcode面试经典150题】73. 从中序与后序遍历序列构造二叉树（C++）
【题目描述】 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。 【示例一】 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]输出：[3,9,20,null,null,15,7] 【示例二】 输入：inorder = ...
学习笔记-数据结构-树与二叉树（2024-04-23）
线索二叉树 传统的二叉链表存储仅能体现一种父子关系，不能直接得到节点在遍历中的前驱或后继。在含有n个节点的二叉树中，有n+1个空指针。这是因为每个叶节点都有2个空指针，每个度为1的节点都有1个空指针，空指针总数为2n0+n1，又因为n0=n2+1，所以空指针的总数为n0+n1+n2+1=n+1。由此设想利用这些空指针来指向其前驱或后继。 引入线索二叉树正是为了加快查找节点前驱和后继的速度。 规定：若无...
C++数据结构与算法——二叉树公共祖先问题
文章目录 一、236. 二叉树的最近公共祖先二、235. 二叉搜索树的最近公共祖先 一、236. 二叉树的最近公共祖先 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(...