首页 > 代码库 > Populating Next Right Pointers in Each Node(I,II)
Populating Next Right Pointers in Each Node(I,II)
以下两种方法均适用于任意结构的树
方法一:使用栈的数据结构
/** * 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) return; stack<TreeLinkNode *> s; s.push(root); while(!s.empty()) { vector<TreeLinkNode *>tmp; TreeLinkNode *prev = s.top(); tmp.push_back(s.top()); s.pop(); while(!s.empty()) { TreeLinkNode *cur = s.top(); tmp.push_back(s.top()); s.pop(); prev->next = cur; prev = cur; } for(int i=tmp.size()-1; i >= 0; --i) { if(tmp[i]->right) s.push(tmp[i]->right); if(tmp[i]->left) s.push(tmp[i]->left); } } } };
方法二:基于层次遍历的方法,使用指针记录下一层首先遍历的节点
/** * 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) { while(root) { TreeLinkNode *next = nullptr; TreeLinkNode *prev = nullptr; for(; root; root = root->next) { if(!next) next = (root->left == nullptr) ? root->right : root->left; if(root->left) { if(prev) prev->next = root->left; prev= root->left; } if(root->right) { if(prev) prev->next = root->right; prev = root->right; } } root = next; } } };
Populating Next Right Pointers in Each Node(I,II)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。