专栏首页米扑专栏【leetcode】Populating Next Right Pointers in Each Node

【leetcode】Populating Next Right Pointers in Each Node

Question :

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

Anwser 1:    Travesal

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root){
            return;
        }

        TreeLinkNode *left = root;
        while(left && left->left && left->right)
        {
            root = left;
            while(root)
            {
                root->left->next = root->right;     // connect two nodes of root
                if(root->next){
                    root->right->next = root->next->left;   // connect two isolated nodes
                }
                    
                root=root->next;    // traversal the same level line
            }
            left=left->left;
        }
    }
};

Anwser 2:    Recursive

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root){
            return;
        }
        
        if(root->left){
            root->left->next = root->right;
        }
        
        if(root->right){
            root->right->next = root->next ? root->next->left : NULL;
        }

        connect(root->left);
        connect(root->right);
    }
};

Anwser 3: Queue

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root){
            return;
        }
        
        queue<TreeLinkNode *> Q;
        if(root != NULL){
            Q.push(root);
        }
        
        int row = 1;
        int count = 0;
        while(!Q.empty()){
            TreeLinkNode *tmp = Q.front();
            Q.pop();
            count++;
            
            if(tmp->left) Q.push(tmp->left);
            if(tmp->right) Q.push(tmp->right);
            
            if(count == row){
                tmp->next = NULL;
                count = 0;
                row *= 2;
            } else {
                tmp->next = Q.front();
            }
        }
    }
};

注意点:

1) Queue > Traversal > Recursive

2) Queue 没有递归的层次限制,可以使用很大的二叉树

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode】Populating Next Right Pointers in Each Node II

    Follow up for problem "Populating Next Right Pointers in Each Node".

    阳光岛主
  • 【leetcode】Path Sum

    Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

    阳光岛主
  • 典型开源3D引擎分类比较

    常见的3D引擎有:Unreal、Quake、Lithtech、OGRE、Nebula、Irrlicht、Truevision3D...

    阳光岛主
  • 【leetcode】Populating Next Right Pointers in Each Node II

    Follow up for problem "Populating Next Right Pointers in Each Node".

    阳光岛主
  • 通过AI及数据能力,助力智慧零售全面数字化升级

    腾讯云智慧门店解决方案,能够通过AI和大数据能力,为线下门店提供包括基于人脸识别、商品识别、商圈分析、口碑管理等场景化能力,帮助零售行业提供智慧收银、门店选址、...

    腾讯云智慧零售
  • 腾讯云胥彪:AI助力零售业连接数字经济未来

    腾讯云智慧门店解决方案,能够通过AI和大数据能力,为线下门店提供包括基于人脸识别、商品识别、商圈分析、口碑管理等场景化能力,帮助零售行业提供智慧收银、门店选址...

    腾讯云智慧零售
  • 大数据开发需要学习哪些技术?

    Java开发介绍、熟悉Eclipse开发工具、Java语言基础、Java流程控制、Java字符串、Java数组与类和对象、数字处理类与核心技术、I/O与反射、多...

    加米谷大数据
  • Dimple在左耳听风ARTS打卡(二十二)

    这周身体有点抱恙,扛过炎热的7月,没想到在8月之初,竟然华丽丽的中暑,哈哈。好在还没想过放弃打卡,等哪天想放弃了,估计还有点舍不得。

    程序员小跃
  • 机器学习算法实现解析——libFM之libFM的模型处理部分

    本节主要介绍的是libFM源码分析的第三部分——libFM的模型处理。 3.1、libFM中FM模型的定义 libFM模型的定义过程中主要包括模型中参数的设置及...

    zhaozhiyong
  • 大数据开发需要学习哪些技术?

    Java开发介绍、熟悉Eclipse开发工具、Java语言基础、Java流程控制、Java字符串、Java数组与类和对象、数字处理类与核心技术、I/O与反射、多...

    加米谷大数据

扫码关注云+社区

领取腾讯云代金券