leetcode 117. 填充每个节点的下一个右侧节点指针 II(二叉树，DFS)

zhuixunfighting 2021-01-19 原文

题目链接

https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/

题目大意

给定一个二叉树

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

给一颗二叉树，要求每个节点与最右边的节点相连接，注意区别：这题和116题意思不太相同，116题还可以保证每个节点的左右子树都存在（除非叶子节点）。
其次，本题难点还在于要求常数的内存空间，这就排除了使用队列进行层次遍历的做法
最后，本题对于递归遍历的顺序还有要求：即需要先遍历右子树，再遍历左子树

在这幅图中，如果先遍历左子树，再遍历右子树，那么从9—1之间的指针在遍历以2为根节点的左子树时没有被连接，这样会造成以7为根节点的右子树0，无法找到右边相邻的8

//本题将条件限制为 二叉树
//与116题注意区分，不一定左子树存在
//注意递归左右子树的区别

class Solution {
public:
    Node *getnext(Node *root){
        if(!root) return  root;
        if(root->left) return root->left;
        if(root->right) return root->right;

        return getnext(root->next);
    }

    Node* connect(Node* root) {
        if(!root) return root;
        if(root->left && root->right) root->left->next=root->right;
        if(root->left && !root->right) root->left->next=getnext(root->next);
        if(root->right) root->right->next=getnext(root->next); //无论左子树是否为空，均需要找到相邻的右子树
        // if(!root->left && root->right) root->right->next=getnext(root->next);

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

初次的做法：

 Node* connect(Node* root) {//注意需要判空 节点位置的信息可能为空
        //怎么维护左边起的第二个节点？？
        // if(!root || !root->left) return root;
        if(!root) return root;
        if(root->left){
            Node *tmp=NULL, *start=root;
            if(start->right) tmp=start->right;
            else{
                while(start->next){
                    if(start->next->left) {
                        tmp=start->next->left;
                        break;
                    }
                    else if(start->next->right){
                        tmp=start->next->right;
                        break;
                    }
                    else{
                        start=start->next;
                    }
                }
            }
            root->left->next=tmp;
        }

        if(root->next){
            if(root->right){
                if(root->next->left)
                    root->right->next=root->next->left;
                else
                    root->right->next=root->next->right;
            }
        }

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