题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
import java.util.*; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { TreeNode head = null; //根节点的前驱接节点 TreeNode pre = null; public TreeNode Convert(TreeNode root) { if(root == null) return null; Convert(root.left); //找到最小的值,初始化pre和head if(pre == null){ head = root; pre = root; }else{ //当前节点与上一节点建立连接,将pre设置为当前值 pre.right = root; root.left = pre; pre = root; } Convert(root.right); return head; } }
思路:
- 对于本题,二叉搜索树,重要是找到最左端节点,即值最小的节点。链表有序,很明显使用中序遍历。
- 由根节点和前驱节点进行连接,不用管节点与右子树节点的连接。递归时候右子树节点就会变成根节点,重新与它的父节点(前驱节点)构建连接关系