首页 > 其他分享 >106. 从中序与后序遍历序列构造二叉树 c

106. 从中序与后序遍历序列构造二叉树 c

时间:2024-03-06 13:23:11浏览次数:26  
标签:遍历 TreeNode struct head1 int inorder 二叉树 106 postorder

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* buidl_tree(int* inorder,int head1,int n1,int* postorder,int head2,int n2){
    if(n1<=0||n2<=0) return NULL;
    struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=postorder[head2+n2-1];
    int i=head1;
    for(;i<head1+n1;i++){
        if(inorder[i]==root->val) break;
    }
    root->left=buidl_tree(inorder,head1,i-head1,postorder,head2,i-head1);
    root->right=buidl_tree(inorder,i+1,n1-i+head1-1,postorder,head2+i-head1,n2-i+head1-1);
    return root;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    return buidl_tree(inorder,0,inorderSize,postorder,0,postorderSize);
}

结果:

标签:遍历,TreeNode,struct,head1,int,inorder,二叉树,106,postorder
From: https://www.cnblogs.com/llllmz/p/18056298

相关文章

  • 654. 最大二叉树c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/intmaxindex(int*nums,inthead,inttail){if(head==tail)returnhead;intmax=head;for(int......
  • 【C++】判断一颗二叉树是否对称
    四步法:(1)如果两个子树都为空指针,则它们相等或对称(2)如果两个子树只有一个为空指针,则它们不相等或不对称(3)如果两个子树根节点的值不相等,则它们不相等或不对称(4)根据相等或对称要求,进行递归处理。//四步法判断一颗二叉树是否对称//主函数boolisSymmetric(TreeNode*root){......
  • 【C++】二叉树的前序、中序、后序遍历(递归、非递归)
    #include<vector>#include<iostream>#include<string>usingnamespacestd;//二叉树的定义structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(inta):val(a),left(NULL),right(NULL){}};//使用递归进行前序遍历voidpreoder(Tr......
  • 【C++】求二叉树的最大深度和最小深度
    //求一颗二叉树的最大深度求高度:后序遍历求深度:前序遍历intmaxDepth(TreeNode*root){returnroot?1+max(maxDepth(root->left),maxDepth(root->right)):0;}//求一颗二叉树的最小深度(实质上是后序遍历)intminDepth(TreeNode*root){if(!root)retur......
  • 【C++】翻转二叉树(递归、非递归)
    //使用递归翻转二叉树TreeNode*reverseTree(TreeNode*root){if(!root)returnroot;swap(root->left,root->right);reverseTree(root->left);reverseTree(root->right);returnroot;}//使用队列翻转二叉树层序遍历TreeNode*invertTree(TreeNode*root)......
  • 代码随想录算法训练营第三十七天 | 738. 单调递增的数字,968.监控二叉树
    968.监控二叉树 已解答困难 相关标签相关企业 给定一个二叉树,我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。 示例1:输入:[0,0,null,0,0]输出:1......
  • 基于preparedStatement对数据的增删改查,以及全自动遍历
    1packagecom.atsyc.api.preparedstatement;23/*4*使用preparedStatement进行t_user表的增删改查动作5*/67importcom.mysql.cj.xdevapi.PreparableStatement;8importorg.junit.Test;910importjava.sql.*;11importjava.util.*;......
  • 257. 二叉树的所有路径c
    很好的题目,让我的sprintf旋转/***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*//***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*......
  • 110. 平衡二叉树c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/intmax(inti,intj){if(i>j)returni;returnj;}intheight(structTreeNode*root){......
  • 代码随想录算法训练营第三十六天| ● 738.单调递增的数字 ● 968.监控二叉树 ● 总
    单调递增的数字 题目链接:738.单调递增的数字-力扣(LeetCode)思路:从左向右验证是否按位单调递增,如果出现递减的区间,则从该位开始验证该位减1后是否比左边的相邻位大,如果不符合就接着向左寻找这样的位,如果找到了,则将该位前面的位复制到结果中,该位减1加入结果,该位之后的位全部改......