1.二叉树展开为链表

题目描述：

给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。 leetcode 114

image.png

后序遍历 + 专注当前结点该做的事情

  1. 拉平左子树
  2. 拉平右子树
  3. root的right指针指向左子树

  4. 遍历到左子树的末尾，将末尾指向root的右子树

    1. class Solution {
    2.  public void flatten(TreeNode root) {
    3.      if(root == null) return;
    5.      flatten(root.left);
    6.      flatten(root.right);
    8.      TreeNode left = root.left; // 保存当前结点的左右子树，放置丢失
    9.      TreeNode right = root.right;
    11.      root.left = null;
    12.      root.right = left;
    14.      TreeNode cur = root;         //遍历到左子树的末尾
    15.      while(cur.right != null){
    16.          cur = cur.right;
    17.      }
    19.      cur.right = right;
    20.  }
    21. }

2.二叉搜索树转换为单向链表

题目描述：

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。 面试题 17

pre指针 + head入口 + 中序遍历 + 区分是否为首结点

  1. 在中序遍历中区分是否是首结点操作
  2. 首结点赋值给前置指针，其他节点进行链表延申

  3. 当前指针前移

    class Solution {
public TreeNode convertBiNode(TreeNode root) {
    inOrder(root);
    return head;
}

TreeNode head = null;
TreeNode pre = null;
public void inOrder(TreeNode root){
    if(root == null) return;

    inOrder(root.left);

    if(pre == null){
        head = root;  // 设置链表入口
    }else{
        pre.right = root; //延长链表
    }

    root.left = null;
    pre = root;   //更新pre

    inOrder(root.right);
}
}

    3.二叉树转换为双向链表

题目描述：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。 要求不能创建任何新的节点，只能调整树中节点指针的指向。 剑指offer 36

image.pngimage.png

与单链表转化完全相同

class Solution {
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;

        inOrder(root);
        head.left = pre;
        pre.right = head;

        return head;
    }

    Node head = null;
    Node pre = null;
    public void inOrder(Node root){
        if(root == null) return;

        inOrder(root.left);//设置链表入口
            head = root;
        }else{              //延长链表
            pre.right = root;
        }

        root.left = pre; //左指针更新
        pre = root; //当前指针更新
        //pre = pre.right; //error 首次操作时会空指针异常


        inOrder(root.right);
    }
}

4.有序链表构建平衡二叉树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 leetcode 109

给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

快慢指针 + 递归构建

public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        return sortedListToBSTCore(head,null);
    }

    public TreeNode sortedListToBSTCore(ListNode head,ListNode tail) {
        if(head == null || head == tail) return null;
        ListNode fast = head;
        ListNode slow = head;

        while(fast != tail && fast.next != tail && fast.next != null && fast != null){
            fast = fast.next.next;
            slow = slow.next;

        }

        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBSTCore(head,slow);
        root.right = sortedListToBSTCore(slow.next,tail);

        return root;
    }