Menu

Subscribe

LeetCode 117 [Populating Next Right Pointers in Each Node II]

ShuyuFang on Leetcode

题目链接

题目描述

  • 给定一颗二叉树，要求将每个结点的next指针指向它右侧的结点，若它右侧没有结点，则指向NULL，处理过程只能使用常量复杂度的空间。

解题思路

  1. 本题与题目116不一样的地方在于给定的二叉树是普通的，除了二叉树的基本特征之外，没有其他可以利用的特点。
  2. 若不限制使用的空间的复杂度，我们就可以通过遍历，把每一层最近一次被访问的结点记录下来，每次访问到同一层的下一个结点，就把记录的同层的结点的next指针指向当前结点，再把当前结点作为本层最近一次被访问的结点记录下来，这样遍历完之后next指针也就构建完毕了。
  3. 对于限制空间复杂度的条件，我们只能通过时间换空间的方式来解决。解决的方式是每一次遍历，目标仅针对特定某一层的结点，具体步骤如下：
    1. 假如根结点深度为0，叶结点最深的深度为h，在进行每一轮遍历之前，将辅助记录本层上一次访问的结点的指针置为NULL。
    2. 进行一轮遍历时，从根结点开始，若当前结点的深度与本次遍历的目标层的深度一致，则对应更新next指针与辅助指针，对于深度超过目标的结点不需要遍历。
    3. 每一轮遍历结束之后，若辅助指针不为NULL，说明需要继续下一轮遍历.
    4. 经过h轮遍历之后，next指针即构建完毕。
  4. 假设二叉树高度为h，则处理过程对树遍历了h轮，设 0 < i <= h，则第i轮最多遍历 sum(2^0 + 2^1 + … + 2^(i-1)) 个结点，第i轮遍历的时间复杂度为O(2^i)，因此最终时间复杂度为O(h * 2^h)。

C++代码

/**
 * 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 travel(TreeLinkNode* node, int height, TreeLinkNode** lastNode, int level) {
    	if (!node) {
    		return;
    	}
    	if (height == level) {
    		if (*lastNode) {
    			(*lastNode)->next = node;
    		}
    		*lastNode = node;
    		return;
    	}
    	travel(node->left, height + 1, lastNode, level);
    	travel(node->right, height + 1, lastNode, level);
    }
    
    void connect(TreeLinkNode *root) {
    	TreeLinkNode* lastNode = NULL;
    	int level = 0;
    	do {
    		lastNode = NULL;
    		travel(root, 0, &lastNode, level);
            level++;
    	} while (lastNode);
    }
};