二叉树的层次遍历BFS

末蓝、 2022-12-15 11:03 132阅读 0赞

使用队列实现BFS  
queue.peek()只获取队首元素不删除  
queue.poll()获取并删除队首元素

/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */
    
    class Solution { 
        public Node connect(Node root) { 
            //队列BFS
            if(root == null){ 
                return null;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            while(!queue.isEmpty()){ 
                int l = queue.size();
                for(int i = 0;i < l;i++){ 
                    Node node = queue.poll();
                    if(i < l - 1){ 
                        node.next = queue.peek();
                    }
                    if(node.left != null){ 
                        queue.add(node.left);
                    }
                    if(node.right != null){ 
                        queue.add(node.right);
                    }
                }
            }
            return root;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70_pic_center]

/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */
    class Solution(){ 
    	public Node connect(Node root){ 
    		if(root == null){ 
    			return null;
    		}
    		Node leftmost = root;
    		while(leftmost.left != null){ 
    			Node head = leftmost;
    			while(head != null){ 
    				head.left.next = head.right;
    				if(head.next != null){ 
    					head.right.next = head.next.left;
    				}
    			head = head.next;
    			}
    			leftmost = leftmost.left;
    		}
    		return root;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/7686a301dd624ae0b0000e3af00767a1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，132人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树的层次遍历

二叉树的层次遍历（Level Order Traversal）是一种广度优先搜索（BFS）的算法，它按照树的层次顺序，逐层遍历二叉树的节点。具体步骤如下： 1. 创建一个队

迈不过友情╰/ 2024年03月17日 21:01/ 0 赞/ 89 阅读

相关二叉树的层次遍历BFS

使用队列实现BFS queue.peek()只获取队首元素不删除 queue.poll()获取并删除队首元素 / // Definition for a No

末蓝、/ 2022年12月15日 11:03/ 0 赞/ 133 阅读

相关层次遍历创建二叉树

1. 树种结点的输入顺序：层序创建–>按树的从上至下从左右的顺序输入，各层的空结，点输入数值0。在构造二叉树过程中，需要一个队列暂时存储各结点的地址。 2. 创建过程：

àì夳堔傛蜴生んèń/ 2022年12月04日 07:49/ 0 赞/ 184 阅读

相关二叉树的层次遍历

[102][]. 二叉树的层序遍历给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。 ![在这里插入图片描述][watermar

港控/mmm°/ 2022年11月26日 09:53/ 0 赞/ 206 阅读

相关二叉树的层次遍历

/二叉树的层次遍历/ include<stdio.h> define MAX 1000 typedef char datatype; t

「爱情、让人受尽委屈。」/ 2022年06月14日 23:56/ 0 赞/ 230 阅读

相关二叉树的层次遍历

题目1 给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。例如: 给定二叉树: \[3,9,20,null,null,15,7\],

迷南。/ 2022年02月27日 14:16/ 0 赞/ 257 阅读

相关二叉树层次遍历

function levelOrder (root) { if (!root){ ret

太过爱你忘了你带给我的痛/ 2022年01月10日 04:57/ 0 赞/ 293 阅读

相关 leetcode:103. 二叉树的锯齿形层次遍历（bfs）

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。例如：给定二叉树 `[3,9,20,null,

Bertha 。/ 2021年09月28日 11:36/ 0 赞/ 282 阅读

相关 leetcode:102. 二叉树的层次遍历(bfs)

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。例如: 给定二叉树: `[3,9,20,null,null,15,7]`, 3

青旅半醒/ 2021年09月28日 11:36/ 0 赞/ 338 阅读

相关二叉树的层次遍历

1.LEETCODE102 二叉树的层次遍历给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。解题思路： 1.逐层添加到队列

╰半橙微兮°/ 2021年09月26日 23:38/ 0 赞/ 400 阅读