二叉搜索树和双向链表
二叉搜索树与双向链表
http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5
二叉搜索树和双向链表
借鉴大佬的代码,牛客id为 ZwZ呀咿呀咿哟
分析如下:
- 有序的双向链表=>中序遍历, 小->大
- 根据要求,节点的left指向小节点,节点的right指向大节点
- 递归的规律出来了,left向小节点,也就是前一个节点
- left指向大节点,那么前一个节点的right指向当前节点
- 头节点就是node.left == null 的节点
private TreeNode treeNode = null ; public void Convert(TreeNode pRootOfTree) { if (pRootOfTree == null){ return null ; }else { Convert(pRootOfTree.left); pRootOfTree.left = treeNode ; //左节点指向小节点 if (treeNode!=null){ treeNode.right = pRootOfTree ;//右节点指向大节点 } treeNode = pRootOfTree ; // 记录上一个遍历到的节点 Convert(pRootOfTree.right); } }