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 };
时间: 10-20

Populating Next Right Pointers in Each Node 设置二叉树的next节点的相关文章

Populating Next Right Pointers in Each Node

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

【56】116. Populating Next Right Pointers in Each Node

116. Populating Next Right Pointers in Each Node Description Submission Solutions Add to List Total Accepted: 118451 Total Submissions: 321021 Difficulty: Medium Contributors: Admin Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLi

leetcode - Populating Next Right Pointers in Each Node I&amp;II

Populating Next Right Pointers in Each Node I 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 nex

LeetCode OJ:Populating Next Right Pointers in Each Node II(指出每一个节点的下一个右侧节点II)

Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example,Given the following binary tr

[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, al

leetcode 117 Populating Next Right Pointers in Each Node II ----- java

Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example,Given the following binary tr

LeetCode[Tree]: Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example, Given the following binary t

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example, Given the following binary t

Populating Next Right Pointers in Each Node II LeetCode

Populating Next Right Pointers in Each Node II Total Accepted: 18934 Total Submissions: 62031My Submissions Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous