内容简介:Given a binary treestruct Node {int val;
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Example:
Input: {"$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":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1} Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1} Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.
Note:
1. You may only use constant extra space. 2. Recursive approach is fine, implicit stack space does not count as extra space for this problem.
难度:medium
题目:给定二叉树,计算结点指向其相邻右结点的下一跳指针。如果没有相邻的右结点则next为NULL.
思路:递归
Runtime: 3 ms, faster than 18.40% of Java online submissions for Populating Next Right Pointers in Each Node II.
Memory Usage: 51.8 MB, less than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node II.
/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} 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) { Node ptr = root; while (ptr != null) { ptr = buildNodeNext(ptr); } return root; } private Node buildNodeNext(Node head) { if (null == head) { return null; } Node nextLevelLeftMost = buildNodeNext(head.next); Node left = head.left; Node right = head.right; if (left != null && right != null) { left.next = right; right.next = nextLevelLeftMost; return left; } if (left != null && right == null) { left.next = nextLevelLeftMost; return left; } if (left == null && right != null) { right.next = nextLevelLeftMost; return right; } return nextLevelLeftMost; } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
挑战程序设计竞赛
秋叶拓哉、岩田阳一、北川宜稔 / 巫泽俊、庄俊元、李津羽 / 人民邮电出版社 / 2013-7-1 / CNY 79.00
世界顶级程序设计高手的经验总结 【ACM-ICPC全球总冠军】巫泽俊主译 日本ACM-ICPC参赛者人手一册 本书对程序设计竞赛中的基础算法和经典问题进行了汇总,分为准备篇、初级篇、中级篇与高级篇4章。作者结合自己丰富的参赛经验,对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解,并介绍了许多实用技巧。每章后附有习题,供读者练习,巩固所学。 本书适合程序设计......一起来看看 《挑战程序设计竞赛》 这本书的介绍吧!