官方题解:LeetCode官方题解
解题思想:
当根节点不为空时,从二叉树根节点开始遍历
判断当前节点是否有左节点,如果不存在左节点,则当前节点向右移一位
如果存在左节点,创建辅助节点指向左节点,判断左节点是否有右节点,如果有右节点,则将辅助节点指向右节点,此时进行拼接操作,即将辅助节点的右节点指向当前节点的右节点,当前节点cur的右节点指向当前节点的左节点,且当前节点的左节点指向为Null
结束上述步骤之后,当前节点向右移一位,之后开始重新执行上述步骤
大致流程:
将左子树插入到右子树的地方
将原来的右子树接到左子树的最右边节点
考虑新的右子树的根节点,一直重复上边的过程,直到新的右子树为 null
代码:
public void flatten(TreeNode root) {
while (root != null) {
//左子树为 null,直接考虑下一个节点
if (root.left == null) {
root = root.right;
} else {
// 找左子树最右边的节点
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
//将原来的右子树接到左子树的最右边节点
pre.right = root.right;
// 将左子树插入到右子树的地方
root.right = root.left;
root.left = null;
// 考虑下一个节点
root = root.right;
}
}
}