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

题目描述:给定一个二叉树:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}初始状态下,所有 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。
【每日寄语】 逃避压力是没有用的,只会让压力更嚣张,勇敢地去面对。