题目描述:
如果不考虑其他因素,直接使用的是中序遍历,将其节点放入到一个list中,然后针对list中的节点进行重新的定义其左子树为null,右子树为下一个节点,代码如下
class Solution {
public TreeNode increasingBST(TreeNode root) {
List<TreeNode> tem = new ArrayList<>();
if(root == null){
return root;
}
s(root, tem);
for (int i = 0; i < tem.size() - 1; i++) {
tem.get(i).left = null;
tem.get(i).right = tem.get(i + 1);
}
tem.get(tem.size() - 1).left = null;
tem.get(tem.size() - 1).right = null;
return tem.get(0);
}
public void s(TreeNode root,List<TreeNode> tem){
if (root == null){
return ;
}
s(root.left, tem);
tem.add(root);
s(root.right, tem);
}
}
换种思路继续
class Solution {
public TreeNode increasingBST(TreeNode root) {
if(root==null){
return null;
}
TreeNode leftNode=increasingBST(root.left);
TreeNode rightNode=increasingBST(root.right);
TreeNode tmpNode =leftNode;
if(leftNode!=null){
while(tmpNode.right!=null){
tmpNode=tmpNode.right;
}
tmpNode.right=root;
}else{
leftNode=root;
}
root.left=null;
root.right=rightNode;
return leftNode;
}
}