解题思路
class Solution {
TreeNode pre = null;
public void flatten(TreeNode root) {
if(root == null)
return ;
TreeNode l = root.left;
TreeNode r = root.right;
// 左子树清空
root.left = null;
// 如果当前root不是根结点,pre就不为null
if(pre != null){
pre.right = root;
}
// 记录先序遍历的前一个结点
pre = root;
flatten(l);
flatten(r);
}
}
解题思路
class Solution {
public void flatten(TreeNode root) {
helper(root);
}
public TreeNode helper(TreeNode root){
if(root == null)
return null;
TreeNode l = helper(root.left);
TreeNode r = helper(root.right);
root.right = l;
root.left = null;
// 将右孩子放在root链表的末尾
TreeNode t = root;
while(t.right != null){
t = t.right;
}
t.right = r;
return root;
}
}