关于java:offer-36-二叉搜索属与双向链表

二叉搜寻属与双向链表

题目剖析

• 排序链表：因为题目要求为排序的双向循环链表，二叉树只有左根右是排序的，左小，根节点，右大满足题目要求，因而应用 中序遍历
• 双向链表：题目要求说左节点是以后节点的前节点 pre，右节点是以后节点的 next
• 循环链表：链表头节点 head 和尾节点 tail 相互指向，head.left = tail,tail.right = head;

• 打印中序遍历

  // 打印中序遍历
  void dfs(Node root) {if(root == null) return;
    dfs(root.left); // 左
    System.out.println(root.val); // 根
    dfs(root.right); // 右
  }

• 中序遍历树的各个节点，而后构建以后节点的左右节点也就是 left 和 right

题解

说来说去就是依照中序遍历，找到头节点而后遍历左子树，找到根节点，而后遍历右子树 完结