LeetCode: 117. Populating Next Right Pointers in Each Node II

LeetCode: 117. 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 tree,

         1
       /  \       2    3
     / \    \     4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

题目大意: 将给定的任意二叉树链接成上图形式。(空间复杂度要求为 O(1))。

解题思路 —— 递归分治

解题思路同 LeetCode: 116. Populating Next Right Pointers in Each Node 题解。需要注意的是,由于这里给定的不是完全二叉树,因此左子树每一层的最右节点和右子树每一层的最左节点不能用之前的方法求解,而需要单独递归的计算。

AC 代码

/** * 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 {
private:
    // 获取 root 第 level 层最右边的节点
    TreeLinkNode* kLevelMostRight(TreeLinkNode* root, int level)
    {
        if(root == nullptr) return nullptr;

        if(level == 0) return root;

        TreeLinkNode* mostRight = kLevelMostRight(root->right, level-1);
        if(mostRight == nullptr) 
        {
            mostRight = kLevelMostRight(root->left, level-1);
        }

        return mostRight;
    }
    // 获取 root 第 level 层最左边的节点
    TreeLinkNode* kLevelMostLeft(TreeLinkNode* root, int level)
    {
        if(root == nullptr) return nullptr;

        if(level == 0) return root;

        TreeLinkNode* mostLeft = kLevelMostLeft(root->left, level-1);
        if(mostLeft == nullptr) 
        {
            mostLeft = kLevelMostLeft(root->right, level-1);
        }

        return mostLeft;
    }
public:
    void connect(TreeLinkNode *root) {
        if(root == nullptr) return ;

        // 分别对左右子树操作
        connect(root->left);
        connect(root->right);

        int level = 0;
        TreeLinkNode* leftTreeRight = kLevelMostRight(root->left, level);
        TreeLinkNode* rightTreeLeft = kLevelMostLeft(root->right, level);

        // 将左子树的每一层的最右边链接到右子树的最左边
        while(leftTreeRight != nullptr && rightTreeLeft != nullptr)
        {
            leftTreeRight->next = rightTreeLeft;
            ++level;
            leftTreeRight = kLevelMostRight(root->left, level);
            rightTreeLeft = kLevelMostLeft(root->right, level);
        }
    }
};
全部评论

相关推荐

点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
兄弟们,实习都是在接各种api,该怎么包装简历
仁者伍敌:感觉我自己做小项目也是各种api啊,我要怎么包装简历
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务