力扣116/117
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
两题的区别在于树是否是完全二叉树
先看116
由于题目要求空间复杂度为常量，因此不能用BFS，否则队列有大小造成空间复杂度为O(n)。因此只能使用递归，这题其实思路上来说比较清晰，root.left连到root.right上，root.right连到root.next.left上
1 2 3 4 5 o / \ o------>o / \ / \ o-->o-->o o
为了方便，直接给出ide上可以跑的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public class one_one_six_ 填充每个节点的下一个右侧节点指针 @Test public void test () Node root = new Node(1 ); root.left = new Node(2 ); root.left.left = new Node(4 ); root.left.right = new Node(5 ); root.right = new Node(3 ); root.right.left = new Node(6 ); root.right.right = new Node(7 ); Node res = connect(root); } public Node connect (Node root) if (root == null || root.left == null ) return root; root.left.next = root.right; if (root.next != null ) root.right.next = root.next.left; connect(root.left); connect(root.right); return root; } class Node public int val; public Node left; public Node right; public Node next; public Node () public Node (int _val) val = _val; } public Node (int _val, Node _left, Node _right, Node _next) val = _val; left = _left; right = _right; next = _next; } } }
117题的区别在于不一定是完全二叉树，也就是存在右节点为空的情况，那么左节点就要直接next到另一颗子树
1 2 3 4 5 o / \ o-->o / / \ o-->o o
那么加上这个判断就行
还有就是必须先递归右子树再递归左子树，原因如下图
1 2 3 4 5 6 7 8 9 10 为什么要先递归右子树，如下图 先递归左子树 先递归右子树 o o / \ / \ o —— o o —— o / / \ / / \ o —— o o o —— o---o / / \ / / \ o o o o--------o o 也就是说，先递归左子树的话第三层的虚线next数据尚未产生，第四层getNext()时也就找不到第四层的虚线next数据
为了方便测试，直接贴ide下的完整代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 public class one_one_seven_ 填充每个节点的下一个右侧节点指针II @Test public void test () Node root = new Node(1 ); root.left = new Node(2 ); root.left.left = new Node(4 ); root.right = new Node(3 ); root.right.right = new Node(5 ); connect(root); } public Node connect (Node root) if (root == null ) return null ; if (root.left != null ){ if (root.right != null ){ root.left.next = root.right; }else { root.left.next = getNext(root.next); } } if (root.right != null ) { root.right.next = getNext(root.next); } connect(root.right); connect(root.left); return root; } private Node getNext (Node node) if (node == null ) return null ; if (node.left != null ) return node.left; if (node.right != null ) return node.right; if (node.next != null ) return getNext(node.next); return null ; } class Node public int val; public Node left; public Node right; public Node next; public Node () public Node (int _val) val = _val; } public Node (int _val, Node _left, Node _right, Node _next) val = _val; left = _left; right = _right; next = _next; } } }
这份代码非常精炼，尤其是getNext函数
其实这道题逻辑上是比较清晰的（root.left.next = root.right;那段），但是递归那段是很难想到的（root.right.next = getNext(root.next);那段）。反正我是这样，递归的题真的头大，尤其是分治，除了回溯中的递归我总结了套路，其他的依题意太灵活，起码我觉得没有做过相似的题目时我是写不出来的，逃~
其他树的题目点击这里
