P181. 树节点的 next 指针

leetcode 116 DFS BFS 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,给你一棵满二叉树,每个树节点额外增加一个 next 指针,指向它右边的节点。一开始所有节点的 next 指针都为空,你要写一个函数处理这棵二叉树,使得所有节点的 next 指针都指向正确的节点。

注意,满二叉树中,所有叶子节点都在最后一层。并且除了叶子节点,所有其他节点都有两个子节点。

// 包含 next 指针的树节点定义
public class Node {
  public int val;
  public Node left, right, next;
}

比如说,给你的满二叉树是:

     0
   /   \
  2     4
 / \   / \
6   8 10  12

一开始每个节点的 next 指针都为空。你要做的就是,让每个节点的 next 指针指向它右边的节点。对于每一层中最后一个节点,由于它右边没有节点,因此它的 next 指针仍然指向空即可。

      0 -> null
   /     \
  2  ->   4 -> null
 / \     / \
6-> 8->10-> 12 -> null

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。