正文 

当前位置： 首页 > 程序 > java教程

二叉树专题(代码片段)

tingxilin tingxilin     2023-04-07     634

关键词：

二叉树中序非递归

  • 从root开始，一直往左孩子走入栈，走到头
  • 倒退回去到有右孩子的点重复上一个步骤，注意，这中间经过的栈扔出去的点，包括最后一个有右孩子的点都要存到ans里面
  • 注意判断stack为空
技术图片 
/**
 * 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 
    vector<int>ans;
public:
    vector<int> inorderTraversal(TreeNode* root) 
        stack<TreeNode*>tree;
        if(root==NULL)
            return ans;
        tree.push(root);
        while(!tree.empty())
        
            TreeNode*stacktop=tree.top();
            while(stacktop->left!=NULL)
            
                tree.push(stacktop->left);
                stacktop=tree.top();
            
            while(!tree.empty() && tree.top()->right==NULL)
            
                stacktop=tree.top();
                tree.pop();
                ans.push_back(stacktop->val);
            
            if(tree.empty())
                return ans;
            stacktop=tree.top();
            ans.push_back(stacktop->val);
            tree.pop();
            tree.push(stacktop->right);
        
        return ans;
    
;
View Code

 

[专题五]二叉树(代码片段)

树结构专题二叉树几种典型运算typedefstructBTNodeintdata;structBTNode*left;structBTNode*right;BTNode;//创建二叉树BTNodeBinaryTree()BTNode*T=(BTNode*)malloc(sizeof(BTNode));T->data=0;returnT;//BinaryEmpty(T):bool判断树是否为空//Root(T):int返回根结点data//构造二叉... 查看详情

leetcode二叉树专题(仅需7道题就可以带你入门二叉树基本玩法)(代码片段)

文章目录一剑指Offer27.二叉树的镜像剑指Offer27.二叉树的镜像--思路--（递归）二剑指Offer28.对称的二叉树剑指Offer28.对称的二叉树--思路--(递归)三剑指Offer55-I.二叉树的深度剑指Offer55-I.二叉树的深度--思路--（递归）... 查看详情

二叉树专题(代码片段)

二叉树中序非递归从root开始，一直往左孩子走入栈，走到头倒退回去到有右孩子的点重复上一个步骤，注意，这中间经过的栈扔出去的点，包括最后一个有右孩子的点都要存到ans里面注意判断stack为空/***Definitionforabinarytreenode.*st... 查看详情

[二叉树专题]力扣144，94,145(代码片段)

力扣144题目给你二叉树的根节点root，返回它节点值的前序遍历。示例1输入：root=[1,null,2,3]输出：[1,2,3]示例2输入：root=[]输出：[]示例3输入：root=[1]输出：[1]示例4输入：root=[1,2]输出：... 查看详情

二叉树-专题

题型一：非递归遍历二叉树后续structnode{boolisfirst;intval;TreeNode*left,*right;node(int_val,bool_isfirst){val=_val;isfirst=_isfirst;this->left=this->right=NULL;}};vector<int>postorderTraversal(TreeNode* 查看详情

剑指offer07重建二叉树(代码片段)

...博客是剑指Offer专题的开篇，分享自己的学习思路，重建二叉树通过两段代码理解其中的思路。剑指Offer07.重建二叉树前置概念：前序：访问根节点，先序遍历左子树，先序遍历右子树；中序：中序遍历左子树，访问根节点，中... 查看详情

二叉树6：迭代法实现二叉树的遍历(代码片段)

我们在《递归迭代和分治》专题就介绍过，递归能做的迭代一定能做，但是可能会比较复杂。但是与递归相比，代码会稍微好理解一些，所以万一面试时实在想不清楚怎么用递归，那就用迭代+栈硬写，... 查看详情

二叉树22：二叉搜索树之一(代码片段)

前面我们挥挥洒洒20多篇一直在分析二叉树，你是否发现我们用的方法有层次遍历，前序遍历，后序遍历，为啥没有中序遍历呢？难道中序不重要？恰恰相反，中序太重要了，我们要单独分专题讨论... 查看详情

二叉树1.二叉树的基本概念

...比前面一个专题的还多。为此，我们不得不将其分为二叉树和其他树两个大模块来分析。二叉树模块自然是分析二叉树的构造、特征、遍历、线索化和各类变来变去的问题。其他树则是平衡树与AVL树、红黑树、堆与优先级队... 查看详情

二叉树(代码片段)

①二叉树的定义：二叉树是由n(n>=0)个结点组成的有限集合，该集合或者为空，或者是由一个根结点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成 ②二叉树的五种不同形态： ③满二叉树（FullBinaryTree）：... 查看详情

数据结构二叉树(代码片段)

二叉树1.DS二叉树--二叉树构建与遍历题目描述输入输出输入样例输出样例参考代码2.DS二叉树--叶子数量题目描述输入输出输入样例输出样例参考代码3.DS二叉树——二叉树之父子结点题目描述输入输出输入样例输出样例参考代码4.... 查看详情

二叉树详解(代码片段)

文章目录二叉树树概念及结构树的概念树的相关概念树的表示二叉树概念及结构概念特殊的二叉树二叉树的性质二叉树的存储结构二叉树链式结构的实现二叉树的遍历前序遍历（先序遍历）中序遍历后序遍历层序遍历二... 查看详情

二叉树概念及遍历(代码片段)

一.两个特殊的二叉树：【1】满二叉树一棵高度为h，且含有2^h-1个节点的二叉树成为满二叉树满二叉树 查看详情

二叉树小结(代码片段)

二叉树算法小结文章目录二叉树算法小结二叉树的遍历递归遍历非递归遍历层序遍历二叉树的翻转判断二叉树是否对称二叉树的最大深度二叉树的最小深度求二叉树的总结点数判断是否是平衡二叉树BFS模板二叉树的遍历递归遍历... 查看详情

二叉树(代码片段)

1.关于二叉树的定义　　在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）。二叉树常被用于实现二叉查找树和二叉堆。　　二叉树的每个结点至... 查看详情

二叉树的相关操作(代码片段)

文章目录计算结点个数计算叶子结点个数二叉树第k层节点个数二叉树深度/高度二叉树查找值为x的节点判断二叉树是否是完全二叉树二叉树销毁在进行操作前先创建一棵二叉树typedefcharBTDataType;typedefstructBinaryTreeNode BTDataTypedata; str... 查看详情

二叉树练习题(代码片段)

文章目录一、965.单值二叉树1、题目描述2、题目代码二、144.二叉树的前序遍历1、题目描述2、题目代码三、104.二叉树的最大深度1、题目描述2、题目代码四、226.翻转二叉树1、题目描述2、题目代码3、方便理解的图五、94.二叉树... 查看详情

面试---算法面试(代码片段)

算法二叉树二叉树的遍历(前序、中序、后序、层序)递归版本非递归版本二叉树的常见oj二叉树的右视图N叉树的层序遍历反转二叉树对称二叉树子树问题二叉树的最近祖先问题二叉树的最大高度问题二叉树的最小深度完全二叉树... 查看详情