new 二叉搜索树与双向链表递归没看懂

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

思路一 非递归 栈

1.核心是中序遍历的非递归算法。 2.修改当前遍历节点与前一遍历节点的指针指向。

import java.util.*; public class Solution { public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null) return null; TreeNode p = pRootOfTree; TreeNode pre=null; boolean isFirst=true; Stack<TreeNode> stack=new Stack<>(); while(p!=null|| !stack.empty()){ while(p!=null){ stack.push(p); p=p.left; } p=stack.pop(); if(isFirst){ pRootOfTree=p; pre=p; isFirst=false; } else{ p.left=pre; pre.right=p; pre=p; } p=p.right; } return pRootOfTree; } }

递归

没怎么看懂

// 记录子树链表的最后一个节点，终结点只可能为只含左子树的非叶节点与叶节点 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; }