找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2570|回复: 8
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Populating Next Right Pointers in Each Node II 】-【刷题...

[复制链接]

21

主题

8

精华

415

积分

高级会员

Rank: 3Rank: 3

积分
415
发表于 10-13-2014 03:42 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
leetcode通道:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

  • You may only use constant extra space.

For example,
Given the following binary tree,

         1       /  \      2    3     / \    \    4   5    7

After calling your function, the tree should look like:

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

本帖被以下淘专辑推荐:

21

主题

8

精华

415

积分

高级会员

Rank: 3Rank: 3

积分
415
 楼主| 发表于 10-13-2014 03:44 PM | 显示全部楼层
这道题因为不允许用 额外空间,所以queue用不了,不能传统的用BFS解决。思路有点难。

每个节点的next节点可以在横向上找到存在的那个节点,无论是父节点next节点的左或者右孩子,又或者是父节点next的next节点的左或者右节点。。。

因此,这道题目首要是找到右孩子的第一个有效的next链接节点,然后再处理左孩子。然后依次递归处理右孩子,左孩子

  1. public class Solution {
  2.     public void connect(TreeLinkNode root) {
  3.         if(root == null) return;
  4.         if(root.left != null){
  5.             if(root.right != null) root.left.next = root.right;
  6.             else{
  7.                 TreeLinkNode rightRoot = root.next;
  8.                 if(rightRoot == null) root.left.next = null;
  9.                 else {
  10.                     while(root.left.next == null && rightRoot != null){
  11.                         if(rightRoot.left != null)
  12.                             root.left.next = rightRoot.left;
  13.                         else if(rightRoot.right != null) root.left.next = rightRoot.right;
  14.                         else root.left.next= null;
  15.                         rightRoot = rightRoot.next;
  16.                     }
  17.                 }
  18.             }
  19.         }
  20.         
  21.         if(root.right != null){
  22.             TreeLinkNode rightRoot = root.next;
  23.             if(rightRoot == null) root.right.next = null;
  24.             else {
  25.                 while(root.right.next == null && rightRoot != null){
  26.                     if(rightRoot.left != null)
  27.                         root.right.next = rightRoot.left;
  28.                     else if(rightRoot.right != null) root.right.next = rightRoot.right;
  29.                     else root.right.next= null;
  30.                     rightRoot = rightRoot.next;
  31.                 }
  32.             }
  33.         }

  34.         connect(root.right);
  35.         connect(root.left);
  36.     }
  37. }
复制代码
回复 支持 反对

使用道具 举报

1

主题

1

精华

97

积分

资深会员

Rank: 2

积分
97
发表于 10-14-2014 07:31 PM | 显示全部楼层
多谢LZ~从右向左,每个node处理自己的子节点
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表