剑指offer—二叉搜索树与双向链表 解答

剑指offer—二叉搜索树与双向链表

题目描述

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

思路

  1. 递归左子树,把左子树头结点储存用于最后返回
  2. 拿到每个左子树最后一个节点(最右下),与上一层根节点连接
  3. 递归遍历右子树,拿到最左下节点,最小的,与根节点连接
  4. 把右子树依次连接根节点

结合代码参考下面的流程

代码

public class Solution {
    public TreeNode Convert(TreeNode root) {
        return dfs(root);
    }
    public TreeNode dfs(TreeNode node){
        if(node==null) return null;//为空返回null
        if(node.left==null&&node.right==null) return node;//为叶子节点返回该节点
        TreeNode p = dfs(node.left);//递归遍历左子树,拿到最左下节点,保存引用
        TreeNode leftLast = p;//拿到每个左子树最后一个节点,可能为做左下节点(右子树为空)也可能为最右下节点
        while(leftLast!=null&&leftLast.right!=null) leftLast = leftLast.right;
        //为子树最后一个节点,与根节点连接
        if(leftLast!=null){
            leftLast.right = node;
            node.left = leftLast;
        }
        //递归遍历右子树拿到最后一个节点
        TreeNode q = dfs(node.right);
        if(q!=null){
            q.left = node;
            node.right = q;
        }
        //p为空返回node根节点,说明左子树为空,否则返回p(最左下节点)
        return p==null?node:p;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/bst-dlinkedlist.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!