关键词:
完全二叉树的层序遍历
题目链接: link.
原题描述
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是完美二叉树。对于深度为 D 的,有 N 个结点的二叉树,若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点,这样的树就是完全二叉树。
给定一棵完全二叉树的后序遍历,请你给出这棵树的层序遍历结果。
输入格式
输入在第一行中给出正整数 N(≤30),即树中结点个数。第二行给出后序遍历序列,为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。
输出格式
在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔,行首尾不得有多余空格。
样例1
输入
8
91 71 2 34 10 15 55 18
输出
18 34 55 71 2 10 15 91
这个题目已经告诉该树是完全二叉树,所以完全二叉树的性质可以直接拿来用,如果当前结点为i,那么左子树结点就为2i,右子树结点为2i+1,完全二叉树除了叶子结点,每个结点的度都为2。
该题与常规思路不同的是,告诉了后序遍历,从最后开始先赋地址。
#include <bits/stdc++.h>
using namespace std;
struct node
int data;
int lc,rc;
arr[35];
void creat(int n)//类似于后序遍历
if(arr[n].lc) creat(arr[n].lc);//先一直沿着左子树递归,没有左儿子之后输入最后的值,然后再看当前的右儿子。
if(arr[n].rc) creat(arr[n].rc);//判断完这一层递归之后,返回上一次调用它的那一层
scanf("%d",&arr[n].data);
int main()
int n;
cin>>n;
for(int i=1;i<=n;i++)
if(i*2<=n) arr[i].lc=i*2;//给树赋结点地址
if(i*2+1<=n) arr[i].rc=i*2+1;
creat(1);
for(int i=1;i<=n;i++)
if(i==n) cout<<arr[i].data<<endl;
else cout<<arr[i].data<<' ';
return 0;
leetcode二叉树的层序遍历(代码片段)
...分别存储到一个vector”(可能不同的人看的着重点不完全相同,我注意到的是以上三个)。二叉树的层序遍历还是比较好搞的, 查看详情
pta7-5完全二叉树的层序遍历(代码片段)
完全二叉树的遍历题目如图所示思路先把后序序列直接填到完全二叉树里面,然后再对这棵二叉树进行调整,使它成为符合要求的完全二叉树。调整方式:直接对这颗二叉树进行后序遍历,然后在访问结点的时候... 查看详情
二叉树的层序遍历
1typedefstructTreeNode*BinTree;2typedefBinTreePosition;3structTreeNode{4ElementTypeData;5BinTreeLeft;6BinTreeRight;7};8BinTreeBT;9voidLevelOrderTraversal(BinTreeBT)//二叉树的层序遍历,用队列方法,一层一层访问的10{11QueueQ; 查看详情
二叉树的层序遍历(代码片段)
107.二叉树的层序遍历II给定一个二叉树,返回其节点值自底向上的层序遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如:给定二叉树[3,9,20,null,null,15,7],3 /\\920/\\157返回其自底... 查看详情
leetcode-102-二叉树的层序遍历
二叉树的层序遍历题目描述:给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。示例说明请见LeetCode官网。来源:力扣(LeetCode)链接:https://leetcode-cn.com/probl...著作权归领扣网络所... 查看详情
nc15二叉树的层序遍历(代码片段)
题目描述二叉树的层序遍历解题思路运用二叉树的层序遍历和二叉树的深度计算的思想;代码展示/***structTreeNode* intval;* structTreeNode*left;* structTreeNode*right;*;*/classSolutionpublic:/****@paramrootTreeNode类*@returnint整型vector 查看详情
102.二叉树的层序遍历
102.二叉树的层序遍历给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。示例1:输入:root=[3,9,20,null,null,15,7]输出:[[3],[9,20],[15,7]]示例2:输入:root=[1]输出:本文来自博客园,作者:Bail... 查看详情
java二叉树的层序遍历(代码片段)
102.二叉树的层序遍历(代码片段)
二叉树的层序遍历给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。示例:二叉树:[3,9,20,null,null,15,7]3/920/157返回其层序遍历结果:[[3],[9,20],[15,7]]/***Defini... 查看详情
102.二叉树的层序遍历(代码片段)
/***Definitionforabinarytreenode.*structTreeNode*intval;*structTreeNode*left;*structTreeNode*right;*;*//***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesa 查看详情
#yyds干货盘点#leetcode-102.二叉树的层序遍历
...出特性,将要遍历的节点放到队列里,实现层序遍历102.二叉树的层序遍历给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。示例1:输入:root=[3,9,20,null,null,15,7]输出:[[3],[9,20],[15,7]]示... 查看详情
二叉树的层序遍历(代码片段)
题目描述:给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。示例:二叉树:[3,9,20,null,null,15,7],3/920/157返回其层次遍历结果:[[3],[9,20],[15,7]] 解题思路:首先我们要知道层序遍... 查看详情
leetcodeno.107二叉树的层序遍历ii
一、题目描述给定一个二叉树,返回其节点值自底向上的层序遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如:给定二叉树[3,9,20,null,null,15,7], 3 /\\ 9 20 / \\ ... 查看详情
二叉树的层序遍历
还没有完善。。。#include"stdafx.h"#include<iostream>#include<queue>#include<vector>#include<math.h>typedefstructBaseNode*tree;structBaseNode BaseNode*left; BaseNode*right; intval; B 查看详情
刷题-力扣-102.二叉树的层序遍历(代码片段)
102.二叉树的层序遍历题目链接来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。题目描述给你一个二叉树,请你返回其... 查看详情
二叉树的层序遍历
全部代码1#include<stdio.h>2#include<stdlib.h>3#include<assert.h>45typedefstructnode6{7intnValue;8structnode*pLeft;9structnode*pRight;10}BiTree;1112typedefstructnode213{14BiTree*nValue;15 查看详情
c++--二叉树的层序遍历(代码片段)
二叉树的层序遍历题目要求:题目来源:力扣classSolutionpublic:vector<vector<int>>levelOrder(TreeNode*root)if(root==nullptr)returnvector<vector<int>>();queue<TreeNode*> 查看详情
107.二叉树的层序遍历ii(代码片段)
力扣打卡:107.二叉树的层序遍历II解题思路正常的层序遍历,最后进行交换即可层序遍历借助的数据结构是:队列首先将root节点加入队列,然后记录此时的长度,因为队列的先进先出,所以需要有一个len记录每一层的数量同一层的遍历... 查看详情