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域指向队首元素,即下一个要访问的结点,这样就将所有结点连成一串了,然后将所有一直靠右的子树的next置位NULL。
C++实现代码如下:
#include<iostream> #include<new> #include<queue> using namespace std; // 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; queue<TreeLinkNode*> q; q.push(root); TreeLinkNode *tmp=root; while(!q.empty()) { tmp->next=q.front(); tmp=q.front(); q.pop(); if(tmp->left) q.push(tmp->left); if(tmp->right) q.push(tmp->right); } tmp->next=NULL; while(root) { root->next=NULL; root=root->right; } } void createTree(TreeLinkNode *&root) { int i; cin>>i; if(i!=0) { root=new TreeLinkNode(i); if(root==NULL) return; createTree(root->left); createTree(root->right); } } }; int main() { Solution s; TreeLinkNode *root; s.createTree(root); s.connect(root); cout<<root->val<<endl; while(root->left) { cout<<root->left->val<<" "; TreeLinkNode *tmp=root->left->next; while(tmp) { cout<<tmp->val<<" "; tmp=tmp->next; } cout<<endl; root=root->left; } }
运行结果:
时间: 2024-09-21 10:25:23