本文主要是介绍leetcode-Populating Next Right Pointers 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
解题思路
/*** 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:void connect(TreeLinkNode *root) {if(root==NULL) return;root->next=NULL;while(root){TreeLinkNode *node=root;while(node&&node->left){node->left->next=node->right;node->right->next=node->next==NULL?NULL:node->next->left;node=node->next;//指向本层的下一个节点}root=root->left;//指向下层的第一个节点}}
};
这篇关于leetcode-Populating Next Right Pointers in Each Node的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!