首页 > 试题广场 >

二叉搜索树与双向链表

[编程题]二叉搜索树与双向链表
  • 热度指数:623998 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。如下图所示


数据范围:输入二叉树的节点数 ,二叉树中每个节点的值
要求:空间复杂度(即在原树上操作),时间复杂度

注意:
1.要求不能创建任何新的结点,只能调整树中结点指针的指向。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构
4.你不用输出双向链表,程序会根据你的返回值自动打印输出

输入描述:
二叉树的根节点


输出描述:
双向链表的其中一个头节点。
示例1

输入

{10,6,14,4,8,12,16}

输出

From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

说明

输入题面图中二叉树,输出的时候将双向链表的头节点返回即可。     
示例2

输入

{5,4,#,3,#,2,#,1}

输出

From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;

说明

                    5
                  /
                4
              /
            3
          /
        2
      /
    1
树的形状如上图       

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
推荐
方法一:非递归版
解题思路:
1.核心是中序遍历的非递归算法。
2.修改当前遍历节点与前一遍历节点的指针指向。
    import java.util.Stack;
    public TreeNode ConvertBSTToBiList(TreeNode root) {
    	if(root==null)
    		return null;
    	Stack<TreeNode> stack = new Stack<TreeNode>();
    	TreeNode p = root;
    	TreeNode pre = null;// 用于保存中序遍历序列的上一节点
    	boolean isFirst = true;
    	while(p!=null||!stack.isEmpty()){
    		while(p!=null){
    			stack.push(p);
    			p = p.left;
    		}
    		p = stack.pop();
    		if(isFirst){
    			root = p;// 将中序遍历序列中的第一个节点记为root
    			pre = root;
    			isFirst = false;
    		}else{
    			pre.right = p;
    			p.left = pre;
    			pre = p;
    		}		
    		p = p.right;
    	}
    	return root;
    }
方法二:递归版
解题思路:
1.将左子树构造成双链表,并返回链表头节点。
2.定位至左子树双链表最后一个节点。
3.如果左子树链表不为空的话,将当前root追加到左子树链表。
4.将右子树构造成双链表,并返回链表头节点。
5.如果右子树链表不为空的话,将该链表追加到root节点之后。
6.根据左子树链表是否为空确定返回的节点。
    public TreeNode Convert(TreeNode root) {
    	if(root==null)
    		return null;
    	if(root.left==null&&root.right==null)
    		return root;
    	// 1.将左子树构造成双链表,并返回链表头节点
    	TreeNode left = Convert(root.left);
    	TreeNode p = left;
    	// 2.定位至左子树双链表最后一个节点
    	while(p!=null&&p.right!=null){
    		p = p.right;
    	}
    	// 3.如果左子树链表不为空的话,将当前root追加到左子树链表
    	if(left!=null){
    		p.right = root;
    		root.left = p;
    	}
    	// 4.将右子树构造成双链表,并返回链表头节点
    	TreeNode right = Convert(root.right);
    	// 5.如果右子树链表不为空的话,将该链表追加到root节点之后
    	if(right!=null){
    		right.left = root;
    		root.right = right;
    	}
		return left!=null?left:root;        
    }
方法三:改进递归版
解题思路:
思路与方法二中的递归版一致,仅对第2点中的定位作了修改,新增一个全局变量记录左子树的最后一个节点。
    // 记录子树链表的最后一个节点,终结点只可能为只含左子树的非叶节点与叶节点
    protected TreeNode leftLast = null;
    public TreeNode Convert(TreeNode root) {
    	if(root==null)
    		return null;
    	if(root.left==null&&root.right==null){
    		leftLast = root;// 最后的一个节点可能为最右侧的叶节点
    		return root;
    	}
    	// 1.将左子树构造成双链表,并返回链表头节点
    	TreeNode left = Convert(root.left);
    	// 3.如果左子树链表不为空的话,将当前root追加到左子树链表
    	if(left!=null){
    		leftLast.right = root;
    		root.left = leftLast;
    	}
    	leftLast = root;// 当根节点只含左子树时,则该根节点为最后一个节点
    	// 4.将右子树构造成双链表,并返回链表头节点
    	TreeNode right = Convert(root.right);
    	// 5.如果右子树链表不为空的话,将该链表追加到root节点之后
    	if(right!=null){
    		right.left = root;
    		root.right = right;
    	}
		return left!=null?left:root;        
    }

编辑于 2015-08-18 23:36:07 回复(111)
public class Solution {
    public TreeNode Convert(TreeNode root) {
     if (root==null)
         return null;
     if(root.left==null&&root.right==null)
         return root;
        //将左子树转换为双向链表
     TreeNode left = Convert(root.left);
     TreeNode p =left;   //返回链表的头结点
     while(p!=null&&p.right!=null)//找到链表的最后一个节点
         {
         p =p.right;
     }
        //如果左子树不为空,将根节点添加其后
        if (left!=null)
            {
            p.right=root;
            root.left=p;
        }
            //将右子树转换为双向链表
     TreeNode right = Convert(root.right);
     //如果右子树不为空,将根节点与右子树进行连接
        if (right!=null)
            {
            root.right=right;
            right.left=root;
        }
            
       return left!=null?left:root;  
    }
}
发表于 2017-04-22 15:09:42 回复(0)
递归中序遍历,左右子树处理不同,左边需要返回最右边的节点,右边需要返回最左边的
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        return fun(pRootOfTree, 1);// 得到最左边节点
    }
    TreeNode fun(TreeNode item, int or) {// 左边0,右边1
		if (item == null) {
			return null;
		}
		TreeNode l = fun(item.left, 0);
		item.left = l;
		if (l != null) {
			l.right = item;
		}
		TreeNode r = fun(item.right, 1);
		item.right = r;
		if (r != null) {
			r.left = item;
		}
		if (or == 1) {// 右子树需要得到最左边节点
			while (item.left != null) {
				item = item.left;
			}
		} else {
			while (item.right != null) {
				item = item.right;
			}
		}
		return item;
	}

}

发表于 2015-10-09 22:33:51 回复(0)
中序遍历即可。只需要记录一个pre指针即可。
高分答案也太绕了吧

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree == nullptr) return nullptr;
        TreeNode* pre = nullptr;
        
        convertHelper(pRootOfTree, pre);
        
        TreeNode* res = pRootOfTree;
        while(res ->left)
            res = res ->left;
        return res;
    }
    
    void convertHelper(TreeNode* cur, TreeNode*& pre)
    {
        if(cur == nullptr) return;
        
        convertHelper(cur ->left, pre);
        
        cur ->left = pre;
        if(pre) pre ->right = cur;
        pre = cur;
        
        convertHelper(cur ->right, pre);
        
        
        
    }
};

发表于 2017-04-12 16:37:03 回复(100)
直接用深度遍历出树的节点,放到list里,再进行排序,再修改指针即可
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
public class Solution {
    ArrayList<TreeNode> list = new ArrayList<>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null ){
            return null;
        }
        dfs(pRootOfTree);
        list.sort( (a,b) ->{
            return a.val - b.val;
        });
        for (int i = 0; i < list.size()-1; i++) {
            list.get(i).right = list.get(i+1);
        }
        list.get(list.size()-1).right = null;
        list.get(0).left = null;
        for (int i = 1; i < list.size(); i++) {
            list.get(i).left = list.get(i-1);
        }
        return list.get(0);
    }

    private void dfs(TreeNode root) {
        if(root == null){
            return;
        }
        list.add(root);
        if(root.left != null){
            dfs(root.left);
        }
        if(root.right != null){
            dfs(root.right);
        }

    }
}


发表于 2021-10-27 16:02:23 回复(0)
class Solution {
public:
    void ConverCore(TreeNode* pCurrent, TreeNode* &pLast)
    {
        if (!pCurrent)return;
        ConverCore(pCurrent->left, pLast);
        /*下面几句是最核心的同剑指offer思想一致
        cur ->left = pre;
        if(pre) pre ->right = cur;
        pre = cur;*******/
        if (!pLast)pCurrent->left = nullptr;//这句其实就是链表第一个点
        else
        {
            pCurrent->left = pLast;
            pLast->right = pCurrent;
        }
        pLast = pCurrent;
        //********
        ConverCore(pCurrent->right, pLast);
    }
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if (!pRootOfTree)return nullptr;
        TreeNode* pLast = nullptr;
        ConverCore(pRootOfTree, pLast);
        TreeNode *pHead = nullptr;
        while (pLast->left)
            pLast = pLast->left;
        pHead = pLast;
        return pHead;
    }
};
编辑于 2018-11-30 10:06:05 回复(1)

本地调试版

#include <iostream>

using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    TreeNode() {}
};

TreeNode* newTree()
{
    TreeNode* node = new TreeNode;
    int x;
    cin >> x;
    if (!x)node = NULL;
    else
    {
        node->val = x;
        node->left = newTree();
        node->right = newTree();
    }
    return node;
}

TreeNode* leftHead = NULL;
TreeNode* rightHead = NULL;

TreeNode* Convert(TreeNode* pRootOfTree)
{
    if (pRootOfTree == NULL) return NULL;
    Convert(pRootOfTree->left);
    if (rightHead == NULL)
        leftHead = rightHead = pRootOfTree;
    else
    {
        rightHead->right = pRootOfTree;
        pRootOfTree->left = rightHead;
        rightHead = pRootOfTree;
    }
    Convert(pRootOfTree->right);
    return leftHead;
}

void print(TreeNode* node)
{
    while (node)
    {
        cout << node->val << " ";
        node = node->right;
    }
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    TreeNode* pRoot = NULL;
    pRoot = newTree();
    print(Convert(pRoot));
    return 0;
}
发表于 2018-06-29 14:38:26 回复(0)
class Solution:
    """使用辅助栈,中序遍历"""
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return
        stack = []
        p = pRootOfTree
        pre = None
        is_first = True
        root = None
        while stack or p:
            while p:
                stack.append(p)
                p = p.left
            p = stack.pop()
            if is_first:
                root = p
                pre = root
                is_first = False
            else:
                pre.right = p
                p.left = pre
                pre = p
            p = p.right
        return root

class Solution:
    """递归,使用辅助实例属性first"""
    flag = 0
    first = None
    pre = None
    def Convert(self, pRootOfTree):
        # write code here
        root = pRootOfTree
        if not pRootOfTree:
            return
        self.Convert(root.left)
        if not self.flag:
            self.first = root
            self.pre = self.first
            self.flag = 1
        else:
            self.pre.right = root
            root.left = self.pre
            self.pre = root
        self.Convert(root.right)
        return self.first

class Solution:
    """不借助实例属性递归"""
    def Convert(self, pRootOfTree):
        # write code here
        root = pRootOfTree
        if not root:
            return
        pre = None
        self.inorder(pRootOfTree, pre)
        while root.left:
            root = root.left
        return root
    def inorder(self, current, pre):
        if not current:
            return pre
        pre = self.inorder(current.left, pre)
        current.left = pre
        if pre:
            pre.right = current
        pre = current
        return self.inorder(current.right, pre)

python的三种实现方式

编辑于 2018-02-01 11:02:52 回复(1)
注意二叉搜索树不一定是平衡的,有可能左子树大、右子树小。!!!!
class Solution {
public:
    TreeNode* Convert(TreeNode* p)
    {
 	if(p==0) return 0;
        if(p->left)
        {
            TreeNode* p0=Convert(p->left);
            while(p0->right!=0)
                p0=p0->right;
            p->left=p0;
            p0->right=p;
        }
        if(p->right)
        {
            TreeNode* p1=Convert(p->right);
            p->right=p1;
            p1->left=p;
        }

        while(p->left!=0)
                p=p->left;
        return p;
    }
};

发表于 2016-06-13 22:44:03 回复(4)
又是一个递归定义的问题。。。好像都这么喜欢递归么。。
typedef TreeNode* ptr;
typedef pair<ptr, ptr> ppp;
class Solution {
    ppp recur(ptr rt){
        if(!rt) return ppp(NULL, NULL);
        ppp l = recur(rt -> left), r = recur(rt -> right);
        if(!l.first) l = ppp(rt, rt);
        else l.second -> right = rt, rt -> left = l.second, l.second = rt;
        if(r.first) l.second -> right = r.first, r.first -> left = l.second, l.second = r.first;
        return l;
    }
public:
    TreeNode* Convert(TreeNode* rt){
        if(!rt) return NULL;
        return recur(rt).first;
    }
};

发表于 2015-08-23 01:26:59 回复(0)
public class Solution {
    public TreeNode Convert(TreeNode root) {
        if(root==null)
            return null;
        get(root);
        while(root.left!=null)
            root = root.left;
        return root;
    }

    public TreeNode get(TreeNode root) {
        if(root.left!=null){
            TreeNode pre = get(root.left);
            while(pre.right!=null)
                pre = pre.right;
            pre.right = root;
            root.left = pre;
        }
        if(root.right!=null){
            TreeNode next = get(root.right);
            while(next.left!=null)
                next = next.left;
            next.left = root;
            root.right = next;
        }
        return root;
    }
}

发表于 2016-04-16 14:13:48 回复(0)
/**
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 realHead = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree);
        return realHead;
    }
    
    private void ConvertSub(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return;
		ConvertSub(pRootOfTree.left);
		if (head == null) {
			head = pRootOfTree;
			realHead = pRootOfTree;
		} else {
			head.right = pRootOfTree;
			pRootOfTree.left = head;
			head = pRootOfTree;
		}
		ConvertSub(pRootOfTree.right);
    }
}

发表于 2015-09-22 15:56:27 回复(69)
Java
思路:
二叉树中序遍历 + 递归

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    // 双向链表左头节点
    private TreeNode leftHead;
    // 双向链表右头节点
    private TreeNode rightHead;

    public TreeNode Convert(TreeNode pRootOfTree) {
        // base case 节点为空时,返回 null
        if (pRootOfTree == null) {
            return null;
        }
        // 先将节点左子树进行转换
        Convert(pRootOfTree.left);
        // 若此时左头节点为空,则将左右头节点均设置为当前节点
        if (leftHead == null) {
            leftHead = pRootOfTree;
            rightHead = pRootOfTree;
        } else {
            // 否则,将当前节点与右头节点连接,并更新右头节点
            rightHead.right = pRootOfTree;
            pRootOfTree.left = rightHead;
            rightHead = pRootOfTree;
        }
        // 将节点右子树进行转换
        Convert(pRootOfTree.right);
        // 返回左头节点
        return leftHead;
    }
}


编辑于 2019-04-17 22:00:35 回复(1)
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        self.list = []
        self.midTree(pRootOfTree)
        if len(self.list)==1:
            return self.list[0]
        for i, node in enumerate(self.list):
            if i != len(self.list) - 1:
                node.right = self.list[i + 1]
                self.list[i + 1].left = node
            else:
                node.left = self.list[i - 1]
        return self.list[0]
    def midTree(self, root):
        if not root:
            return
        self.midTree(root.left)
        self.list.append(root)
        self.midTree(root.right)

发表于 2017-12-06 15:32:43 回复(0)
public class Solution {
    TreeNode head, pre;
    public TreeNode Convert(TreeNode pRootOfTree) {
        //中序遍历,在访问每个节点时构建cur和前驱节点pre的引用指向
        if(pRootOfTree == null) return null;
        dfs(pRootOfTree);
        return head;
    }
    void dfs(TreeNode cur) {
        if(cur == null) return ;
        dfs(cur.left);
        if(pre != null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}
发表于 2022-08-01 19:41:22 回复(0)
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    pre = None 
    head = None 
    def Convert(self, pRootOfTree):
        # write code here
        # 中序遍历时改变指向
        self.pre = None 
        self.head = None 
        
        def midorder(node):
            if node is None:
                return None 
            midorder(node.left)
            
            if not self.pre:
                self.pre = node
                self.head = node 
                node.left = None 
            else:
                self.pre.right = node 
                node.left = self.pre 
                self.pre = node 
            
            midorder(node.right)
            
        midorder(pRootOfTree) 
        return self.head 

发表于 2022-04-08 19:58:39 回复(0)
题目要求:空间复杂度O(1)(即在原树上操作),时间复杂度 O(n)。
很多同学用栈或递归的方式中序遍历二叉树,实际上都是不满足题目要求的。这道题只能用Morris遍历。

public TreeNode Convert(TreeNode pRootOfTree) {
  TreeNode head = new TreeNode(0);
  TreeNode tail = head;
  for (TreeNode ptr = pRootOfTree; ptr != null; ) {
    if (ptr.left != null) {
      TreeNode mostRight = ptr.left;
      while (mostRight.right != null && mostRight.right != ptr) {
        mostRight = mostRight.right;
      }
      if (mostRight.right == null) {
        mostRight.right = ptr;
        ptr = ptr.left;
      } else {
        mostRight.right = null;
        tail.right = ptr;
        ptr.left = tail;
        tail = ptr;
        ptr = ptr.right;
      }
    } else {
      tail.right = ptr;
      ptr.left = tail;
      tail = ptr;
      ptr = ptr.right;
    }
  }
  head = head.right;
  if (head != null) head.left = null;
  return head;
}

发表于 2022-03-09 12:23:49 回复(0)
class Solution:
    def Convert(self , pRootOfTree ):
        self.pre = None
        def dfs(root, pre):
            if root.left:
                dfs(root.left, self.pre)
            if self.pre is None:
                head.left = root
                root.left = None
            else:
                root.left = self.pre
                self.pre.right = root
            self.pre = root
            if root.right:
                self.pre.right = root.right
                dfs(root.right, self.pre)
        if pRootOfTree is None:
            return None
        head = TreeLinkNode(-1)
        dfs(pRootOfTree, self.pre)
        return head.left
pre指针必须为全局变量
发表于 2022-03-04 15:41:18 回复(0)
class Solution {
public:
    TreeNode* head = new TreeNode(-1);
    TreeNode* pre = head;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree) return nullptr;
        dfs(pRootOfTree);
        //head->left = nullptr;
        head->right->left = nullptr;
        return head->right;
        
    }
    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->left);
        pre->right = root;
        root->left = pre;
        pre = root;
        dfs(root->right);
    }
};

发表于 2022-02-26 01:19:15 回复(0)
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        //二叉搜索树的中序遍历是排序的
        if (pRootOfTree == null) {
            return null;
        }
        //将二叉搜索树转换成一个双向链表
        inOrderConvert(pRootOfTree);
        //别忘了原来的根节点可不是现在的双向链表的头结点!赶快移过去!
        TreeNode head = pRootOfTree;
        while (head.left != null){
            head = head.left;
        }
        return head;
    }

    TreeNode prev = null;//记录当前已经修改的节点
    public void inOrderConvert(TreeNode root){
        if (root == null){
            return;
        }
        inOrderConvert(root.left);
        //要想将其转化为双向链表,只需在中序遍历的过程中修改left和right的指向
        //left -> 双向链表的前驱 prev
        //right -> 双向链表的后继 next
        root.left = prev;
        if (prev != null){
            //第一个不需要,否则null.right会报空指针异常
            prev.right = root;
        }
        prev = root;
        inOrderConvert(root.right);
    }
}

发表于 2022-02-12 12:12:45 回复(0)
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    map<int, TreeNode*> m;
    vector<int> v;
    void bianli(TreeNode* root){
        if(!root) return;
        bianli(root->left);
        m[root->val] = root;
        v.push_back(root->val);
        bianli(root->right);
        return;
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree) return {};
        bianli(pRootOfTree);
        m[v[0]]->right = m[v[1]];
        m[v[v.size()-1]]->left = m[v[v.size()-2]];
        for(int i=1;i<v.size()-1;i++){
            m[v[i]]->left = m[v[i-1]];
            m[v[i]]->right = m[v[i+1]];
        }
        return m[v[0]];
    }
};
发表于 2021-07-20 17:22:48 回复(0)