二分搜索树转双向链表(牛客JZ36)
题目
思路
1,对二分搜索树进行中序遍历
2,将二分搜索树左节点和根节点相连接,右节点和根节点相连接
遍历左子树,连接(左子树尾部不为空)
leftTail.right = pRootOfTree;
pRootOfTree.left = leftTail;
遍历右子树,连接
right.left = pRootOfTree;
pRootOfTree.right = right;
代码实现
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null ||(pRootOfTree.left == null && pRootOfTree.right == null)){
return pRootOfTree;
}
TreeNode left = Convert(pRootOfTree.left);
TreeNode leftTail = left;
while(leftTail != null && leftTail.right != null){
leftTail = leftTail.right;
}
//将二分搜索树左节点和根节点相连
//左子树尾部不为空
if(leftTail != null) {
leftTail.right = pRootOfTree;
pRootOfTree.left = leftTail;
}
TreeNode right = Convert(pRootOfTree.right);
//将二分搜索树右节点和根节点相连
if(right != null){
right.left = pRootOfTree;
pRootOfTree.right = right;
}
return left == null?pRootOfTree:left;
}