首页 > 代码库 > Populating Next Right Pointers in Each Node 设置二叉树的next节点
Populating Next Right Pointers in Each Node 设置二叉树的next节点
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设置为右侧相邻节点。
解决思路：
一次对每个节点进行遍历，若左右子树不为空，则将左子树的next指向右子树，若该节点的next为空，则将右子树的next设置为空(看图分析)
若该节点的next不为空，则指向与该节点同层次中相邻的右侧节点的左子树(看图分析)
这里使用一个队列，将根节点先放入队列，从队列中取出一个节点node，node移除队列，node子树的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 == NULL) return;13 queue<TreeLinkNode *> q;14 15 root->next = NULL;16 17 q.push(root);18 19 while(!q.empty()){20 TreeLinkNode *node = q.front();21 q.pop();22 23 if(node->left != NULL && node->right != NULL){24 q.push(node->left);25 q.push(node->right);26 27 node->left->next = node->right;28 if(node->next == NULL)29 node->right->next = NULL;30 else{31 TreeLinkNode *node_next = q.front();32 node->right->next = node_next->left;33 }34 35 }36 37 }38 39 }40 };
Populating Next Right Pointers in Each Node 设置二叉树的next节点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。