欢迎光临散文网 会员登陆 & 注册

LeetCode-117-填充每个节点的下一个右侧节点指针 II

2021-11-22 10:01 作者:雄狮虎豹  | 我要投稿

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

题目描述:给定一个二叉树:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

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

示例说明请见LeetCode官网。

来源:力扣(LeetCode)   

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

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:层序遍历

求解过程和 LeetCode-116-填充每个节点的下一个右侧节点指针 这道题完全一样,现在想想,116题中提到完美二叉树,应该使用完美二叉树的一些性质有更优的解法,而当前的解法是通用的二叉树的解法。

  • 首先,如果root为空或者左右子节点都为空,则不需要处理next指针,直接返回root。

  • 否则,当二叉树不只有一个节点时,利用队列对二叉树进行层序遍历记录二叉树每一层的节点,然后按顺序处理当前层每一个节点的next指针。由于处理过程中所有的节点顺序并没有进行改变,所以最后返回root。

【每日寄语】 逃避压力是没有用的,只会让压力更嚣张,勇敢地去面对。



LeetCode-117-填充每个节点的下一个右侧节点指针 II的评论 (共 条)

分享到微博请遵守国家法律