填充每个节点的下一个右侧节点指针

约定不等于承诺〃 2022-09-14 02:35 140阅读 0赞

LeetCode117题  
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：  
struct Node \{  
int val;  
Node \*left;  
Node \*right;  
Node \*next;  
\}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。  
初始状态下，所有 next 指针都被设置为 NULL。

示例：  
![在这里插入图片描述][197b8c250afa4b15b1d3f473b3bf4723.png]  
输入：root = \[1,2,3,4,5,6,7\]  
输出：\[1,\#,2,3,\#,4,5,6,7,\#\]  
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，’\#’ 标志着每一层的结束

struct NodeNum {
        
        Node* root;
        int step;
        NodeNum(Node* root_, int step_) : root(root_), step(step_) {
        }
    };
    
    class Solution {
        
    public:
        Node* connect(Node* root) {
        
            if (!root) return nullptr;
            queue<NodeNum> q;
            q.push(NodeNum(root, 0));
            Node* last_node = nullptr;
            int last_step = 0;
            while(!q.empty()) {
        
                NodeNum nodenum = q.front();
                q.pop();
                Node* cur = nodenum.root;
                int step = nodenum.step;
                if (step != last_step) {
        
                    last_node = nullptr;
                    last_step = step;
                }
                cur->next = last_node;
                last_node = cur;
                if (cur->right) {
        
                    q.push(NodeNum(cur->right, step + 1));
                }
                if (cur->left) {
        
                    q.push(NodeNum(cur->left, step + 1));
                }
            }
            return root;
        }
    };

[197b8c250afa4b15b1d3f473b3bf4723.png]: /images/20220828/e34e726db25249a2ad1d8223d5e350a9.png