内容简介:给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:struct Node {int val;
题目
给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
示例:
输入:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1} 输出:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1} 解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。
题解
方法一: 层序遍历
使用层序遍历,遍历的时候把同层的节点连接起来;
class Solution { public Node connect(Node root) { if (root == null) return null; Queue<Node> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); Node current = null; while (size > 0) { Node node = queue.poll(); if (node.right != null) queue.add(node.right); if (node.left != null) queue.add(node.left); node.next = current; current = node; size--; } } return root; } }
方法二:递归
递归的时候我们通常就分解为递归子问题和递归结束条件。
递归子问题
- 左右子树分别连起来
递归结束条件
- node == null, 直接返回
- node.left != null, 把left.next连到node.right
- node.right != null && node.next != null, 把node的right 连到 node.next的left。例如遍历到2这个节点,把5连接到6.
class Solution { public Node connect(Node root) { // o(1) space. if (root == null) return null; if (root.left != null) root.left.next = root.right; if (root.right != null && root.next != null) root.right.next = root.next.left; connect(root.left); connect(root.right); return root; } }
方法三: 层序遍历 o(1)空间复杂度
层序遍历我们之前用队列来做,但是有时候我们会要求层序遍历用常数的空间复杂度来解。这种方法最关键的地方在于理解 如何从上一层切换到下一层的 。dummy的作用用于记录上一层的第一个节点是谁,每当遍历完一层之后,切到下一层.
class Solution { public Node connect(Node root) { Node dummy = new Node(0); Node pre = dummy; Node currentRoot = root; while (currentRoot != null) { if (currentRoot.left != null) { pre.next = currentRoot.left; pre = pre.next; } if (currentRoot.right != null) { pre.next = currentRoot.right; pre = pre.next; } currentRoot = currentRoot.next; if (currentRoot == null) { // 切换层. pre = dummy; currentRoot = dummy.next; dummy.next = null; } } return root; } }
热门阅读
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- AES 算法(三):填充模式
- mybatis自动填充时间字段
- laravel 使用 Faker 数据填充
- Faker 虚拟数据填充和源码解析
- 如何去除讨厌的Chrome自动填充黄色背景
- [ Laravel 5.7 文档 ] 数据库操作 —— 数据填充
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Building Web Reputation Systems
Randy Farmer、Bryce Glass / Yahoo Press / 2010 / GBP 31.99
What do Amazon's product reviews, eBay's feedback score system, Slashdot's Karma System, and Xbox Live's Achievements have in common? They're all examples of successful reputation systems that enable ......一起来看看 《Building Web Reputation Systems》 这本书的介绍吧!