LeetCode

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

题目描述

image.png

LeetCode - 图2

思路：二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情，

函数定义：输入两个节点，将它俩连接起来

  1. class Solution {
  2.     // 主函数
  3.     public Node connect(Node root) {
  4.         if (root == null) return null;
  5.         // 遍历「三叉树」，连接相邻节点
  6.         traverse(root.left, root.right);
  7.         return root;
  8.     }
  10.     // 三叉树遍历框架
  11.     void traverse(Node node1, Node node2) {
  12.         if (node1 == null || node2 == null) {
  13.             return;
  14.         }
  15.         /**** 前序位置 ****/
  16.         // 将传入的两个节点穿起来
  17.         node1.next = node2;
  19.         // 连接相同父节点的两个子节点
  20.         traverse(node1.left, node1.right);
  21.         traverse(node2.left, node2.right);
  22.         // 连接跨越父节点的两个子节点
  23.         traverse(node1.right, node2.left);
  24.     }
  25. }
  26. // 详细解析参见：
  27. // https://labuladong.github.io/article/?qno=116