博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
116. Populating Next Right Pointers in Each Node
阅读量:6930 次
发布时间:2019-06-27

本文共 2986 字,大约阅读时间需要 9 分钟。

Given a binary tree

struct TreeLinkNode {      TreeLinkNode *left;      TreeLinkNode *right;      TreeLinkNode *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.

Note:

  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,

Given the following perfect binary tree,

1       /  \      2    3     / \  / \    4  5  6  7

After calling your function, the tree should look like:

1 -> NULL       /  \      2 -> 3 -> NULL     / \  / \    4->5->6->7 -> NULL

时间复杂度:o(n) 空间复杂度:O(1),因为记录了next指针,可以在层里查找同层的下一个元素,在做层序遍历时不用用到queue,减少了时间复杂度。

机智,即使是相同的办法,在不同的条件下,可以有优化。比如这题里,想想为啥层序遍历要用queue,为了找到上一层的下一个元素。如果有了next指针,不用queue也能找到上一层的下一个元素,得到一个优化解法。 30%

/** * Definition for binary tree with next pointer. * public class TreeLinkNode { *     int val; *     TreeLinkNode left, right, next; *     TreeLinkNode(int x) { val = x; } * } */public class Solution {    public void connect(TreeLinkNode root) {        if (root == null) {            return;        }        root.next = null;        TreeLinkNode prevLevelStart = root, prev, cur;        while (prevLevelStart.left != null) {            prev = prevLevelStart;            cur = prevLevelStart.left;            while (prev != null) {                if (cur == prev.left) {                    cur.next = prev.right;                } else {                    prev = prev.next;                    if (prev == null) {                        cur.next = null;                    } else {                        cur.next = prev.left;                    }                }                cur = cur.next;            }            prevLevelStart = prevLevelStart.left;        }    }}

 相当与层序遍历,在遍历一层时,把一层里的元素前后连起来。 9% 时间+空间复杂度: O(n)

/** * Definition for binary tree with next pointer. * public class TreeLinkNode { *     int val; *     TreeLinkNode left, right, next; *     TreeLinkNode(int x) { val = x; } * } */public class Solution {    public void connect(TreeLinkNode root) {        ArrayDeque
queue = new ArrayDeque
(); if (root == null) { return; } int size = 0, i = 0; TreeLinkNode tmp = null; queue.offer(root); while (!queue.isEmpty()) { size = queue.size(); i = 0; while (i < size) { tmp = queue.poll(); if (tmp.left != null) { queue.offer(tmp.left); } if (tmp.right != null) { queue.offer(tmp.right); } if (i != size - 1) { tmp.next = queue.peek(); } else { tmp.next = null; } i++; } } }}

 

转载于:https://www.cnblogs.com/yuchenkit/p/7192626.html

你可能感兴趣的文章
安卓开发笔记——关于文件断点续传
查看>>
XP系统取消开机硬件检查
查看>>
群发项目设计图
查看>>
Kickoff - 创造可扩展的,响应式的网站
查看>>
UWP?UWP! - Build 2015有些啥?(1)
查看>>
HighCharts 具体使用及API文档说明
查看>>
php中的$_GET怎样获取带有井号“#”的參数
查看>>
Js 冒泡事件阻止
查看>>
总结jQuery选择器
查看>>
Java的super调用案例: super.getClass()返回的是子类自己
查看>>
NYOJ 709(ZZULIOJ1481) 异 形 卵
查看>>
PHP编译支持mysqli
查看>>
使用DLL进行不同语言之间的调用(转)
查看>>
android:scaleType属性
查看>>
Statement和PreparedStatement的区别; 什么是SQL注入,怎么防止SQL注入? (转)
查看>>
UNABLE TO PURGE A RECORD(二)
查看>>
【转载】注释AFX_MSG_MAP,AFX_DATA,AFX_DATA_MAP , Afx_MSG等宏不能删除
查看>>
Spring Bean范围 示例
查看>>
What is a UINavigationTransitionView
查看>>
Solr DIH以Mysql为数据源批量创建索引
查看>>