/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if(root==null) return null;
dfs(root);
pre.right = head;
head.left =pre;//进行头节点和尾节点的相互指向,这两句的顺序也是可以颠倒的
return head;
}
public void dfs(Node cur){
if(cur==null) return;
dfs(cur.left);
cur.left = pre;//pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。
//pre用于记录双向链表中位于cur左侧的节点,即上一次迭代中的cur,当pre==null时,cur左侧没有节点,即此时cur为双向链表中的头节点
if(pre==null) head = cur;
//反之,pre!=null时,cur左侧存在节点pre,需要进行pre.right=cur的操作。
else pre.right = cur;
pre = cur;//pre指向当前的cur
dfs(cur.right);//全部迭代完成后,pre指向双向链表中的尾节点
}
// 作者:jyd
// 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/
}
上一篇

144. 二叉树的前序遍历给你二叉树的根节点 root ,返回它节点值的 前序_ _遍历。
class Solution {
List<Integer> res=new ArrayList<>();
2021-02-28
下一篇

剑指 Offer 36. 二叉搜索树与双向链表输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转
2021-02-27