唔，今天阳光正好，微风不燥。我站在阳台吹了好久的风，也没看清以后的路。
闲话不提，先把今日份的三道题刷完。
二叉树展开为链表
题目：给定一个二叉树，原地将它展开为链表。
题目截图
思路：讲真，我觉得这个题目的重点是原地展开吧。本来一审题觉得是个蛮简单的题目。。后来看了已给代码觉得也没想的那么简单。单纯展开就是一个前序排列的结果，但是说到原地。。。啧啧啧，我可能是题意没太理解，我先照着想的试试代码吧。
回来了，我也不知道为啥看着挺简单的一道题我写的这么恶心，反正是实现了，我先贴出来：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if(root==null) return;
TreeNode cur = root;
LinkedList<Integer> pre = new LinkedList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while(cur !=null || !stack.isEmpty()){
if(cur!=null){
pre.add(cur.val);
stack.add(cur);
cur = cur.left;
}else{
cur = stack.pop();
cur = cur.right;
}
}
pre.removeFirst();
for(int i : pre){
root.left = null;
root.right = new TreeNode(i);
root = root.right;
}
}
}
如上代码，先前序遍历，然后重新改变root的构造，也不知道算不算在原地更改的，毕竟没有直接root=新树。。。真的我现在才发现我对于很多题目上的要求不是很懂，我直接去看看人家的代码吧。
看到了一种很优雅的代码，是递归实现的，我这里先中序再一个个挂很麻烦，其实这个题可以直接挂，挂的准则跟中序差不多，对于每一个非叶子节点来说，先把右节点保存，然后左节点挂在右节点的位置上，左节点清空，然后指针往下指到最下面的叶子节点，再把之前保存的右节点挂上。说起来很复杂，其实我画个草图就好明白了:
草图
其实这个是比较无脑的草图，可以抠细节，比如如果本来左节点就没有了，则不需要操作了。其次我这里简单的root = root.right.但是如果左节点本身不是叶子节点是应该继续处理的。这里应该直接指到当前的叶子节点再操作，应该用while一直指到最后一个节点。但是大体思路就是这么个过程。我直接贴大神代码了：
class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
flatten(root.left);
flatten(root.right);
TreeNode tmp = root.right;
root.right = root.left;
root.left = null;
while(root.right != null) root = root.right;
root.right = tmp;
}
}
喏，就是我又压栈又遍历又重新各种建树的，，，人家这么几行代码，，简洁明了，真的大写的服。哈哈，下一题了。
填充每一个节点的下一个右侧节点指针
题目：给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
题目截图
提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
思路：首先这个题目很长，所以有点考验我的阅读能力，其次提示中递归解题符合要求，说明这道题用递归是一个思路。第一反应是这个，然后正儿八经解题思路是遍历树，然后同一层的除了最后一个分别把next给加上。因为涉及到next是每一层的右边那个节点，所以我觉得应该是层次遍历。但是题目说了要常量额外空间，这就有点难了，具体怎么实现我去尝试写写代码。
有点烦躁！！！递归是递归了，但是我还是觉得我用额外空间了，，，蓝瘦：
/*
// Definition for a Node.
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;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root==null) return root;
List<Node> l = new ArrayList<Node>();
l.add(root);
dfs(l);
return root;
}
public void dfs(List<Node> list){
if(list.size()==0) return;
List<Node> l = new ArrayList<Node>();
for(int i = 0;i<list.size()-1;i++){
list.get(i).next = list.get(i+1);
if(list.get(i).left!=null)l.add(list.get(i).left);
if(list.get(i).right!=null)l.add(list.get(i).right);
}
if(list.get(list.size()-1).left!=null)l.add(list.get(list.size()-1).left);
if(list.get(list.size()-1).right!=null)l.add(list.get(list.size()-1).right);
dfs(l);
}
}
而且自己都觉得写得恶心，其实一个显示队列的调用能直接解决问题，，，我也不知道这么多此一举各种麻烦算不算是符合题目要求的。。。难受，我决定用我自己的方式好好写一下代码，至于额外空间，我到时候还是看题解吧。我去写我自己满意的版本了：
class Solution {
public Node connect(Node root) {
if(root==null) return root;
Queue<Node> quque = new LinkedBlockingQueue<Node>();
quque.add(root);
while(!quque.isEmpty()){
int size = quque.size();
for(int i = 0;i<size;i++){
Node n = quque.poll();
if(i!=size-1)n.next = quque.peek();
if(n.left!=null)quque.add(n.left);
if(n.right!=null) quque.add(n.right);
}
}
return root;
}
}
咳，反正我自认为代码是优雅了，就是性能没法看了，，，我直接看性能排行第一的代码了。
！！！！看完人家的代码我觉得自己可能是个傻子。。这个题简单的出人意料！！我之前一直陷入一个误区，就是一个根节点的左右节点是可以找到下一个的，但是如果是相差很多节点的，需要右节点连接子节点要怎么找到呢，然后就卡死在这，都是每一层每一层的遍历。。。现在看了人家的代码才发现，其实从父节点的next就可以获取当前节点的next。。。我真的是，这个就是思路问题，我去重写了。
class Solution {
public Node connect(Node root) {
if(root==null) return root;
if(root.left!=null && root.right!=null){
root.left.next = root.right;
if(root.next!=null){
root.right.next = root.next.left;
}
connect(root.left);
connect(root.right);
}
return root;
}
}
直接贴代码并自闭五分钟。。。下一题了。
题目：给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
题目截图
思路：额，这个题和上个题，除了不完美就没别的了，但是感觉不能沿用上面的代码了，因为判断上一个节点的下一个节点可能就轮空了，我画个草图。所以怎么处理我还是要想想，其实感觉判断下一个节点如果是叶子节点则继续往下判断就行了。不过这么想的话，判断有点多啊，不是实现不了，我先去试试。
草图
好了，其实在第一道题的基础上改动思路还是好很多的，我直接贴代码：
/*
// Definition for a Node.
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;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root==null) return root;
if(root.right!=null){
if(root.left!=null) root.left.next = root.right;
if( root.next!= null){//右节点连下一个节点
root.right.next = nextNode(root.next);
}
}else if(root.left!=null){
if( root.next!= null){//没有右节点则直接左节点连下一个节点
root.left.next = nextNode(root.next);
}
}
connect(root.right);
connect(root.left);
return root;
}
//获取下一个节点
private Node nextNode(Node node) {
while (node != null) {
if (node.left != null) {
return node.left;
}
if (node.right != null) {
return node.right;
}
node = node.next;
}
return null;
}
}
因为我觉得不是很难，所以也没啥好讲的，这个和上一道题比就是条件判断多了而已。哦，对了有一点就是先递归右节点再递归左节点。
这个顺序仔细想想就能知道为什么。因为是递归，如果先递归左节点，到了需要右节点底下的节点时就没了。这样会丢失指向。我在画个图。
草图
- 如图所示，第一个递归，把标1的指向指向好了。
- 第二次递归，根节点变成了紫色节点，然后把两个红色节点的指向做好了，也就是标做2的线。
- 第三次递归，先左后右的话，左边红色节点作为根节点，吧两个蓝色节点指向做好了。
- 重点来了，第四次递归，因为左边遍历完了，该右节点，所以根节点是右边红色节点（叶子节点直接pass了），这个时候两个黄节点之间的线可以连，但是第二黄色节点从父节点找到的那个节点没有子节点，再往下找线没连呢。。。所以就自动以为没节点了。所以错误就来了。
额，说这么多是为了解释为什么必须先递归右节点而不是常规的左节点。。所以这个题就这样了。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！！另外周末愉快！
网友评论