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

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

LeetCode: Populating Next Right Pointer in Each Node

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

地址:

算法:用递归好简单有木有。按上面的例子,先完成左右子树的连接,然后,根的next指向空,第二个节点指向第三个节点,第五个节点指向第六个节点。代码:

1 /** 2  * Definition for binary tree with next pointer. 3  * struct TreeLinkNode { 4  *  int val; 5  *  TreeLinkNode *left, *right, *next; 6  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     void connect(TreeLinkNode *root) {12         if(!root)   return ;13         root->next = NULL;14         connect(root->left);15         connect(root->right);16         TreeLinkNode *p = root->left;17         TreeLinkNode *q = root->right;18         while(p && q){19             p->next = q;20             p = p->right;21             q = q->left;22         }23     }24 };

第二题:

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

地址:

算法:这道题与前面一题不同的是,这里的二叉树不再是完美二叉树,而是一颗普通的二叉树。由于是一颗普通的二叉树,所以沿着右指针走不一定会到达下一层的最后一个节点,因为这个右指针可能为空;同样,沿着左指针走也不一定会到达下一层的第一个节点,因为这个左指针可能为空。所以,我们需要一个找到当前节点下一层的第一个节点的函数,然后顺着next也可以到达该层的最后一个节点。利用这样的函数,我们就可以完成题目的要求。代码:

1 /** 2  * Definition for binary tree with next pointer. 3  * struct TreeLinkNode { 4  *  int val; 5  *  TreeLinkNode *left, *right, *next; 6  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     void connect(TreeLinkNode *root) {12         if(!root)   return ;13         root->next = NULL;14         connect(root->left);15         connect(root->right);16         TreeLinkNode *p = root->left;17         TreeLinkNode *q = root->right;18         while(p && q){19             TreeLinkNode *r = nextLevelFirst(p);20             while(p->next){21                 p = p->next;22             }23             p->next = q;24             p = r;25             q = nextLevelFirst(q);26         }27     }28     TreeLinkNode * nextLevelFirst(TreeLinkNode *p){29         while(p){30             if(p->left){31                 return p->left;32             }else if(p->right){33                 return p->right;34             }35             p = p->next;36         }37         return NULL;38     }39 };

 

posted on
2014-08-26 22:01 阅读(
...) 评论(
...)

转载于:https://www.cnblogs.com/boostable/p/leetcode_populating_next_right_pointer_in_each_node.html

你可能感兴趣的文章
Total Command 常用快捷键
查看>>
ionic 调用手机的打电话功能
查看>>
怎么使用阿里云直播服务应用到现在主流直播平台中
查看>>
Xcode全局替换内容,一键Replace
查看>>
1000 加密算法
查看>>
exif_imagetype() 函数在linux下的php中不存在
查看>>
Ruby的case语句
查看>>
Linux的链接文件-ln命令
查看>>
maven的tomcat插件如何进行debug调试
查看>>
table表头固定
查看>>
截取字符串中两个字符串中的字符串
查看>>
spring xml properties split with comma for list
查看>>
判断点是否在三角形内
查看>>
Android实战简易教程-第二十三枪(基于Baas的用户注冊验证username是否反复功能!)...
查看>>
在odl中怎样实现rpc
查看>>
leetcode 110 Balanced Binary Tree
查看>>
python活用isdigit方法显示系统进程
查看>>
项目开发总结
查看>>
知行合一
查看>>
jmeter插件之jsonpath提取响应结果和做断言
查看>>