首页 > 代码库 > leetcode Populating Next Right Pointers in Each Node
leetcode Populating Next Right Pointers in Each Node
看图就知道想要做什么事了。
Given a binary tree
struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; }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都是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).
要求常数额外空间。
一个递归就搞定了，就是递归让每一个节点他的左右子树通过next链接，直至到最后一层，然后递归左右节点，继续让他们的左右子树通过next链接。
/** * Definition for binary tree with next pointer. * struct TreeLinkNode { * int val; * TreeLinkNode *left, *right, *next; * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} * }; */class Solution {public://每一层把left的right的next设置为right的leftvoid lr2rl(TreeLinkNode *root){ if (!root) return; TreeLinkNode *lr = root -> left, *rl = root -> right; while(lr && rl) { lr -> next = rl; lr = lr -> right; rl = rl -> left; } lr2rl(root -> left); lr2rl(root -> right);} void connect(TreeLinkNode *root) { lr2rl(root); }};
leetcode Populating Next Right Pointers in Each Node
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。