精华内容
下载资源
问答
  • public class Tree {//头节点private Nodehead;public NodegetHead() {return head;}public void setHead(Node head) {this....}/*** 层遍历* @param head 头节点*/public void floorPrint(Node head){//创建一个队...

    public class Tree {

    //头节点

    private  Nodehead;

    public NodegetHead() {

    return head;

    }

    public void setHead(Node head) {

    this.head = head;

    }

    /**

    * 层遍历

    * @param head  头节点

    */

    public  void  floorPrint(Node  head){

    //创建一个队列

    List queue=new LinkedList();

    queue.add(head);

    //队列不是空的,就一直循环

    while(!queue.isEmpty()){

    Node  n = ((LinkedList)queue).pop();

    //打印元素值

    System.out.println(n.getValue());

    if(Objects.nonNull(n.getLeft())){

    queue.add(n.getLeft());

    }

    if(Objects.nonNull(n.getRight())){

    queue.add(n.getRight());

    }

    }

    }

    public static  void main(String[]  args){

    Node  head =new Node("a");

    Node  son1 =new Node("b");

    Node  son2 =new Node("c");

    head.setLeft(son1);

    head.setRight(son2);

    Node  son3 =new Node("d");

    Node  son4 =new Node("e");

    son1.setLeft(son3);

    son1.setRight(son4);

    Node  son5 =new Node("f");

    Node  son6 =new Node("g");

    son2.setLeft(son5);

    son2.setRight(son6);

    Tree  t =new Tree();

    t.floorPrint(head);

    }

    }

    展开全文
  • 103. 二叉树的锯齿形层次遍历给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / 9 ...

    2764f5f372fec66ad1d788275cd84376.png

    103. 二叉树的锯齿形层次遍历

    给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

    示例: 给定二叉树 [3,9,20,null,null,15,7],

        3
       / 
      9  20
        /  
       15   7

    返回锯齿形层次遍历如下:

    [
      [3],
      [20,9],
      [15,7]
    ]

    作者:力扣 (LeetCode) 链接:https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefh1i/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    题解:

    本题还是基于层序遍历的框架,题目所说的锯齿遍历,就是一行是正序,一行是反序,这种情况设置一个count变量,来隔行判断本行应该正序还是反序存储。

    具体代码如下:

    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new LinkedList<>();
            if (root == null) {
                return result;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int count = 0;
    
            while (!queue.isEmpty()) {
                LinkedList<Integer> temp = new LinkedList<>();
                int len = queue.size();
                for (int i = 0; i < len; i++) {
                    TreeNode node = queue.poll();
                    if (count % 2 != 0) {
                        //头插元素,即逆序
                        temp.add(0, node.val);
                    } else {
                        temp.add(node.val);
                    }
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                count++;
                result.add(temp);
            }
            return result;
        }
    }
    展开全文
  • 前两天说过二叉树的前序遍历、中序遍历、后续遍历,把剩下的也都说了吧,二叉树遍历系列四,层次遍历。题目链接:二叉树层次遍历 - 力扣(LeetCode)​leetcode-cn.com题目描述:给定一个二叉树,返回其按层次遍历...

    d6357da87fb45db4a5ab69b7c052e81b.png

    前两天说过二叉树的前序遍历、中序遍历、后续遍历,把剩下的也都说了吧,二叉树遍历系列四,层次遍历。

    题目链接:

    二叉树的层次遍历 - 力扣(LeetCode)​leetcode-cn.com
    bc242c77d1d18a31c14718fdaf5105c9.png

    题目描述:

    给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

    例如:
    给定二叉树: [3,9,20,null,null,15,7],

        3
       / 
      9  20
        /  
       15   7

    返回其层次遍历结果:

    [
      [3],
      [9,20],
      [15,7]
    ]

    解题思路:

    不同于之前前中后序使用栈的方法,层序遍历我们使用队列。如果一个节点有左右孩子,就把它的左右孩子 push 到队列中。

    代码如下:

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            if(!root) return {};
            vector<vector<int>> res;
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty()){
                vector<int> v;
                int size = q.size();
                for(int i = 0; i < size; ++i){
                    TreeNode* p = q.front();
                    v.push_back(p->val);
                    if(p->left) q.push(p->left);
                    if(p->right) q.push(p->right);
                    q.pop();
                }
                res.push_back(v);
            }
            return res;
        }
    };
    

    leetcode 里还有俩题也是关于二叉树的层次遍历的,一是二叉树的层次遍历 II,是把二叉树的元素按层次的顺序自底向上输出一遍,其实就是把本题最后的结果倒序一下就行了。二是二叉树的锯齿形层次遍历,就是先从左到右,再从右到左,注意按照奇偶性,倒序每一行的元素就行,其他部分和本题完全一致,所以就不单独写一篇了。

    如果有任何疑问,欢迎提出。如果有更好的解法,也欢迎告知。

    展开全文
  • 本以为树开始觉得差不多了,就是个递归或者用队列,没想到笔试居然要用层次遍历建立二叉树,然后按前序遍历输出,以前建树都是递归。所以这道题就gg,后来自己又想的做出来了 */ 题目意思是输入一个层次序列:0,1,2,3,...
    /*
    本以为树开始觉得差不多了,就是个递归或者用队列,没想到笔试居然要用层次遍历建立二叉树,然后按前序遍历输出,以前建树都是递归。所以这道题就gg,后来自己又想的做出来了
    */
    题目意思是输入一个层次序列:0,1,2,3,#,#,4,#,5,6,#
             输出先序序列:0,1,3,#,5,#,#,#,2,#,4,6,#,#,#
    我的输出最后多个,号,但是思路是这样,反序列化二叉树,然后序列化二叉树
    #include<iostream> 
    #include<vector>
    #include<string>
    #include<sstream>
    
    using namespace std;
    
    struct TreeNode
    {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x):val(x),left(NULL),right(NULL){}
    };
    TreeNode* CreateTree(string &str)//层次遍历建立二叉树
    {
    	int num = 0;
    	vector<TreeNode *>tmp;
    	int i;
    	for (i = 0; i < str.length();)
    	{
    		if (str[i] == ',')
    			i++;
    		else
    		if (str[i] == '#')
    		{
    			tmp.push_back(NULL);
    			i++;
    			num++;
    		}
    		else
    		{
    			int x = 0;
    			while (str[i] != ','&&i<str.length())
    			{
    				x = x * 10 + str[i] - '0';
    				i++;
    			}
    			TreeNode *node = new TreeNode(x);
    			tmp.push_back(node);
    			num++;
    		}
    	}
    	int q = 0;//设置BFS层次一个一个处理结点
    	int p = 1;//设置每一棵树得左子树。
    	while (q < num)
    	{
    		if (tmp[q] == NULL)
    			q++;
    		else
    		{
    			if (p < num)
    				tmp[q]->left = tmp[p];
    			if (p + 1 < num)
    				tmp[q]->right = tmp[p + 1];
    			p = p + 2;
    			q++;
    		}
    	}
    	return tmp[0];
    }
    void PreTree(TreeNode *root)//先序排列
    {
    	if (root == NULL)
    	{
    		cout << "#" << ",";
    		return;
    	}
    	cout << root->val << ",";
    	PreTree(root->left);
    	PreTree(root->right);
    }
    int main()
    {
    	string str;
    	cin >> str;
    	if (str == "")
    		return 0;
    	TreeNode *root = CreateTree(str);
    	PreTree(root);
    	return 0;
    }
    

     

    展开全文
  • 本文首发于公众号「五分钟学算法」,是图解 LeetCode 系列文章之一。...题目描述给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如: 给定二叉树 ...
  • 本文首发于公众号「五分钟学算法」,是图解 LeetCode 系列文章之一。...题目描述给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。例如...
  • java根据层次遍历建立二叉树

    千次阅读 2016-01-08 11:43:00
    层次遍历建立二叉树,这里使用的递归的方法,当然也可以建立一个队列来初始化这个二叉树! package Tree; import java.io.*; public class Erchashu { public static BTNode<Integer> BuildTree(int[] tree...
  • 给一棵二叉树的层序遍历序列和中序遍历序列,求这棵二叉树的先序遍历序列和后序遍历序列。 Input 每个输入文件中一组数据。 第一行一个正整数N(1<=N<=30),代表二叉树的结点个数(结点编号为1~N)。接...
  • ** ...** 初看此问题有点小懵逼,因为书上一般都是按先中后序建立,但仔细想想可以根据父亲节点与孩子结点编号的关系来建立二叉树。** 接收输入,初始化,定义一个指针数组来存储节点,并且数组下
  • 二叉树采用二叉链表结构表示。设计并实现如下算法:输入某棵二叉树的广义表形式,建立二叉树,并按层次遍历二叉树
  • 二、已知层次遍历顺序,构建二叉树。(链式存储) 三、已知节点关系,建立二叉树(邻接表存储) 四、已知先序和中序遍历顺序,建立二叉树。 前提知识: 约定: 约定二叉树的内容为int类型,并且都>=1,0...
  • 1.二叉树层次遍历 2.二叉树结构图的打印 结语 1.二叉树层次遍历 主要用到队列操作,先入队根结点,再不断出队,判断出队结点是否有左右孩子,有则入队,直到队列空为止。 层次遍历挺简单,但是如果要输出结点...
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式: 输入第一行给出一个正整数NN(\le 30≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。...
  • 不管是二叉树建立 求前遍历 后遍历 还是层次遍历,都是利用中序遍历的性质 和一个前序遍历或后序遍历,讲一个节点的左支所有的数,右支所有的数,和该节点的数分开,然后根据题目重新排序; 前序遍历:该节点的...
  • 层次遍历创建二叉树

    2020-09-06 19:43:25
    #include <iostream>...//新定义二叉树类型 typedef ElementType int; //用0表示没有结点 #define NoInfo 0 struct TNode{ ElementType data; BinTree left; BinTree Right; }; BinTree
  • 中序遍历,层次遍历构建二叉树

    千次阅读 2017-03-01 10:37:59
    问题 C: 还原二叉树时间限制: 1 Sec内存限制: 128 MB提交: 324解决: 155提交状态题目描述给一棵二叉树的层序遍历序列和中序遍历序列,求这棵二叉树的先序遍历序列和后序遍历序列。输入每个输入文件中一组数据。...
  • 层次遍历数组建立二叉树

    千次阅读 2018-10-06 11:26:06
    层次遍历数组建立二叉树 约定:层次遍历数组中为空的结点记为0 解析 使用递归,检查每个结点的左右结点是否存在,存在即分配结点,并递归检查该结点。 void insert(TreeNode *p, vector&lt;int&gt; ...
  • /** 15 15 7 20 -1 -1 3 12 -1 -1 -1 -1 14 8 -1 -1 2 4 */ import java.util.*; public class Main2 { static int[] value ; static class TreeNode{ int val; TreeNode left,right;... t.
  • 掌握二叉树的二叉链表存储结构;...设计并实现如下算法:输入某棵二叉树的广义表形式,建立二叉树,并按层次遍历二叉树----队列形式   #include #include #include #define STACK_MAX_SIZ
  • 给出一个层次遍历,和一个中序遍历的结果字符串 层次 A B C D E F G 中序 D B A F E G C 其对应的二叉树是:  A  / /  B C  / /  D E  / /  F G 【算法思想】 用LEV代表层次遍历MID代表中序...
  • 层次遍历二叉树

    2015-06-29 23:17:51
    层次遍历二叉树 void CreateBiTree(BiTree &T) //先序法建立二叉树 { char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) exit(OVERFLOW); T->data=ch;...
  • 根据前序遍历,我们可以确定该二叉树的根节点为A,再通过中序遍历中A的位置,可以确定DGB为该二叉树的左子树,ECF为右子树 根据这个逻辑,每次在前序遍历中读取一个节点,再在中序遍历中找到他所在的位置,便可以...
  • 按照层序遍历建树是树的基本操作之一。通常用创建队列,逐层加入元素检查某层是否满,直到发现空位置的方法解决。本代码增加一种输入’#'字符的情况,表明该节点存储的数据为空。 #构造二叉树并实现访问操作,输入#...
  • void CreatebiTree(BiTree *BT){ SqStack s;BiTree p,e;int Flag=1;char ch;initstack(&s); *BT=NULL; scanf("%c",&ch); while (ch !=#) { switch(ch) { case (: { Push(&s,p); Flag = 1;...
  • PTA - 按层次遍历二叉树

    千次阅读 2019-05-19 16:27:06
    读入相应先序序列,建立二叉树,然后按层次遍历该二叉树并输出结点数据。 输入格式: 字符串形式的先序序列(即结点的数据类型为单个字符) 输出格式: 按层次遍历二叉树的结果 输入样例: 在这里给出一组输入。例如: ...
  • package com.atguigu.springboot.bean.binary; import sun.reflect.generics.tree.Tree; import java.util.*; class TreeNode { TreeNode left; TreeNode right; int val;...public class CreateTwo.
  • 读入相应先序序列,建立二叉树,然后按层次遍历该二叉树并输出结点数据。 输入格式: 字符串形式的先序序列(即结点的数据类型为单个字符) 输出格式: 按层次遍历二叉树的结果 输入样例: 在这里给出一组输入。例如: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,454
精华内容 5,381
关键字:

层次遍历建立二叉树