[leetcode] 116. Populating Next Right Pointers in Each Node

[leetcode] 116. Populating Next Right Pointers in Each Node

Description

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node { int val; Node *left; Node *right; Node *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.

Example:

Input:

{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Output:

{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

Explanation:

Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

You may only use constant extra space.Recursive approach is fine, implicit stack space does not count as extra space for this problem.

分析

题目的意思是：给你一棵完全二叉树，把每个节点指向每一层的右节点，如果节点没有右节点，则置空。

递归和非递归都可以做，非递归模拟的是栈，递归很简洁，需要手手工模拟一下，个人感觉不怎么好理解。

代码-递归

/** * 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) { if(!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); }};

代码-非递归

/** * 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) { if(!root) return; TreeLinkNode *p=root,*q; while(p->left){ q=p; while(q){ q->left->next=q->right; if(q->next){ q->right->next=q->next->left; } q=q->next; } p=p->left; } }};

参考文献

​​[编程题]populating-next-right-pointers-in-each-node​​​​[LeetCode] Populating Next Right Pointers in Each Node 每个节点的右向指针​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。