正文

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

recoverableti  recoverableti  2023-04-23  179

关键词：

树结构专题

二叉树

几种典型运算

typedef struct BTNode
  int data;
  struct BTNode *left;
  struct BTNode *right;
BTNode;
// 创建二叉树
BTNode BinaryTree() 
  BTNode *T = (BTNode*)malloc(sizeof(BTNode));
  T->data = 0;
  return T;

//BinaryEmpty(T):bool 判断树是否为空
//Root(T):int 返回根结点data
//构造二叉树
BTNode MakeTree(int x, BTNode *l, BTNode *r) 
  BTNode *T = (BTNode*)malloc(sizeof(BTNode));
  T->data = x;
  T->left = l; T->right = r;
  return T;

//BreakTree(x,T,l,r):void makeTree的逆运算 拆成左右树

先序非递归

//PreOrder(root):void 先序遍历
//PreOut(root):void 先序序列
void PreOrder(BTNode *root) 
  if(!root) exit(1);
  stack<BTNode*> stack;
  BTNode *cur;
  stack.push(root);
  while(!stack.empty()) 
    cur = stack.top();
    stack.pop();
    cout << cur->data << " ";
    if (cur->right) 
      stack.push(cur->right);
    
    if (cur->left) 
      stack.push(cur->left);

中序非递归 — 记忆区别 1

//InOrder(root):void 中序遍历
//InOut(root):void 中序序列
void InOrder(BTNode *root) 
  if(!root) exit(1);
  stack<BTNode*> stack;
  // 与先序区分
  BTNode *cur = root;
  while(!stack.empty() || cur) 
    while (cur) 
      stack.push(cur);
      cur = cur->left;
    
    if (!stack.empty()) 
      cur = stack.top();
      stack.pop();
      cout << cur->data << " ";
      cur = cur->right;

后序非递归

//先序左右孩子入栈顺序交换得到逆后序，逆后序再逆序得后序
//PostOrder(root):void 后序遍历
//PostOut(root):void 后序序列
void PostOrder(BTNode *root) 
  if(!root) exit(1);
  stack<BTNode*> stack1;
  stack<BTNode*> stack2;
  BTNode *cur;
  stack1.push(root);
  while(!stack1.empty()) 
    cur = stack1.top();
    stack1.pop();
    stack2.push(cur);
    if (cur->left)  /*左右孩子入栈顺序改变*/
      stack1.push(cur->left);
    
    if (cur->right) 
      stack1.push(right);
    
  
  while (!stack2.empty()) 
    cur = stack2.top();
    cout<< cur->data << " ";
    stack2.pop();

层序遍历可记录层数

void LevelOrder(BTNode *root) 
  queue<BTNode*> que;
  BTNode *cur;
  que.push(root);
  while (!que.empty()) 
    int size = que.size(); // 嵌套for循环使用
    while (!que.empty()) 
      cur = que.front();
      que.pop();
      if (cur->left) 
        que.push(cur->left);
      
      if (cur->right) 
        que.push(cur->right);

中序遍历的二叉树线索化 — 记忆

/** 首先明确是使用递归，传入的是pre和root
    对于某结点而言，如果它没有左孩子，则左线索指向前驱
    同理 如果它的前驱没有右孩子，则指向后继
    然后使pre指针后移一位，而中序遍历中，本结点后继是右孩子，所以p移向右孩子
  **/
void Inthread(BTNode *p, BTNode *&pre) 
  if (p) 
    Inthread(p->left, pre);
    if (p->left==NULL) 
      p->left = pre;
      p->ltag = 1;
    
    if (pre!=NULL && pre->right==NULL) 
      pre->right = p;
      p->rtag = 1;
    
    pre = p;
    Inthread(p->rchild, pre);

二叉搜索树

二叉搜索树基本操作 — 记忆

/** 根据BST的特性，对于每个节点：如果目标值等于节点的值，则返回节点;如果目标值小于节点的值，则继续在左子树中搜索;如果目标值大于节点的值，则继续在右子树中搜索。 **/

// 增加结点
TreeNode* insertIntoBST(TreeNode* root, int val) 
        TreeNode *p = root, *pre;
        while(p)  /**先搜索，边保存前驱结点**/
            pre = p;// 保存前驱很重要！！
            if(p->val>val) p = p->left;
            else if(p->val<val) p = p->right;
            else return 0;
        
        TreeNode *r = new TreeNode(val); //创建结点
        if(root)  /**如果树存在，则创建前驱结点与新结点的关系，反之，则将该结点插入空树**/
            if(pre->val > val) pre->left = r;
            else pre->right = r;
        
        else root = r;
        return root;
    

// 删除结点 我无能，抄大佬的递归
TreeNode* deleteNode(TreeNode* root, int key) 
        if(root==NULL)return NULL;
        if(root->val>key)
        
            root->left = deleteNode(root->left,key);
            return root;
        
        if(root->val<key)
        
            root->right = deleteNode(root->right,key);
            return root;
        
        if(root->left==NULL&&root->right==NULL)return NULL;
        if(root->left==NULL&&root->right!=NULL)return root->right;
        if(root->left!=NULL&&root->right==NULL)return root->left;
        int val = findMax(root->left);
        root->val=val;
        root->left = deleteNode(root->left,val);
        return root;
    
    int findMax(TreeNode* root)
    
        if(root->right==NULL)return root->val;
        return findMax(root->right);

二叉树的路径最大和

// lmr讨论的是 包含a作为根结点的结果 可能       
int maxs = INT_MIN;
    int maxPathSum(TreeNode* root) 
        findroot(root);
        return maxs;
    
    int findroot(TreeNode *root) 
        if(!root) return 0;
        int left = max( findroot(root->left), 0); //用这种方法舍去左右孩子可能为负值的情况
        int right = max( findroot(root->right), 0);
        int lmr = root->val + right + left;
        maxs = max(maxs, lmr);  
        // 如果大于0 说明可以使分支变大 太难了
        return max(0,root->val + max(left, right));

知识点和代码均学习于Acwing: https://www.acwing.com/activity/

数据结构面试题及答案讲解：二叉树专题（上）(代码片段)

数据结构面试题及答案讲解：二叉树专题（上）本节目标1、求二叉树的最大深度。（2018年腾讯面试题）2、判断一个二叉树是否是高度平衡的二叉树。（2020年字节跳动面试真题）3、根据一棵树的前序遍历与中序遍历构造二叉树... 查看详情

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

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

二叉树专题(代码片段)

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

二叉树基础题解(代码片段)

二叉树基础题一.相同的树思路代码二.另一棵树的子树思路代码三.二叉树的最大深度思路代码四.平衡二叉树思路代码五.对称二叉树思路代码这些问题都有一个类TreeNode。publicclassTreeNodeintval;TreeNodeleft;TreeNoderight;TreeNode()TreeNode(intva... 查看详情

二叉树(代码片段)

/*6.5二叉树二叉树具有五种基本形态：1.空二叉树。2.只有一个根节点。3.根结点只有左子树。4.根结点只有右子树。5.根节点既有左子树又有右子树。特殊二叉树：1.斜树斜树一定要是斜的，但是往哪斜还是有讲究，所有结点都只... 查看详情

leetcode刷穿二叉树(代码片段)

二叉树我又双叒叕来啦～专辑完结，欢迎查看本系列文章：leetcode刷穿二叉树（一）leetcode刷穿二叉树（二）leetcode刷穿二叉树（三）leetcode刷穿二叉树（四）leetcode刷穿二叉树（五ÿ... 查看详情

leetcode刷穿二叉树（完结）(代码片段)

完全掌握二叉树只需要六天专辑完结，欢迎查看本系列文章：leetcode刷穿二叉树（一）leetcode刷穿二叉树（二）leetcode刷穿二叉树（三）leetcode刷穿二叉树（四）leetcode刷穿二叉树（五）... 查看详情

仅不到五万字轻松了解二叉树和堆(代码片段)

...x1f4a6;树在实际中的运用(表示文件系统的目录树结构)二、二叉树概念及结构💦二叉树的概念💦特殊的二叉树💦二叉树的性质💦二叉树的概念选择题💦二叉树的存储结构三、二叉树顺序结构及实现💦二叉... 查看详情

[二叉树专题]力扣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* 查看详情

数据结构学习笔记——线索二叉树(代码片段)

目录一、线索二叉树的结点结构二、线索二叉树的定义三、中序线索二叉树的遍历四、先序线索二叉树的遍历五、后序线索二叉树的遍历一、线索二叉树的结点结构在由n个结点组成的二叉链表中，含有n+1个空指针域，... 查看详情

数据结构学习笔记——线索二叉树(代码片段)

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

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

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

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

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

...要？恰恰相反，中序太重要了，我们要单独分专题讨论。1.从二分查找说起我们在递归迭代和分治部分分析过二分查找。二分法的查找过程是，在一个有序的序列中查看详情

数据结构二叉树经典oj练习(代码片段)

目录前言1.单值二叉树2.相同的树3.对称二叉树4.二叉树的前序遍历5.另一棵树的子树6.平衡二叉树 7.二叉树遍历前言本章只是二叉树的部分简单练习，对于这部分题目大多比较简单，但重要的不是能过OJ，而是深入理解... 查看详情

n日一篇——二叉树(代码片段)

目录一、用接口实现二叉树的抽象数据类型二、辅助类栈（自己编辑的）队列（自己编辑的）ArrayList（JavaAPI的）三、实现二叉树+先序遍历+中序遍历+后序遍历+用栈实现先序遍历+用栈实现中... 查看详情

leetcode刷穿二叉树(代码片段)

...xff01;专辑完结，欢迎查看本系列文章：leetcode刷穿二叉树（一）leetcode刷穿二叉树（二）leetcode刷穿二叉树（三）leetcode刷穿二叉树（四）leetcode刷穿二叉树（五）leetcode刷穿二叉树࿰... 查看详情

正文

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

树结构专题

二叉树

几种典型运算

先序非递归

中序非递归 — 记忆区别 1

后序非递归

层序遍历 可记录层数

中序遍历的二叉树线索化 — 记忆

二叉搜索树

二叉搜索树基本操作 — 记忆

二叉树的路径最大和

数据结构面试题及答案讲解：二叉树专题（上）(代码片段)

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

二叉树专题(代码片段)

二叉树基础题解(代码片段)

二叉树(代码片段)

leetcode刷穿二叉树(代码片段)

leetcode刷穿二叉树（完结）(代码片段)

仅不到五万字轻松了解二叉树和堆(代码片段)

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

二叉树-专题

数据结构学习笔记——线索二叉树(代码片段)

数据结构学习笔记——线索二叉树(代码片段)

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

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

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

数据结构二叉树经典oj练习(代码片段)

n日一篇——二叉树(代码片段)

leetcode刷穿二叉树(代码片段)

层序遍历可记录层数