力扣面试150题-- 二叉树展开为链表

Day 46

题目描述

思路

初次做法：由于我直接考虑O（1）级别的空间复杂度，于是采取了以下做法：

1. 接下来的内容就是递归函数
2. 如果该节点为空，就返回null
3. 将此时的current作为头节点，left和right作为孩子节点，先左后右遍历
4. 此时我们就需要处理儿子节点的，如果此时左孩子不为空。我们就将原来的右孩子接到这个左孩子的向下遍历的最后一个右孩子的后面，将左孩子变成右孩子（说着有点绕，看代码就行）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public void flatten(TreeNode root) {change(root);}private void change(TreeNode root) {if (root == null) return;// 保存原始左右子树（防止递归中被修改）TreeNode left = root.left;TreeNode right = root.right;// 先递归处理左子树（以current作为新的父节点）change(left);// 再递归处理右子树（以current作为新的父节点）change(right);// 处理子节点：将左子树的尾部连接到右子树if (left != null) {// 找到左子树的最右节点（链表尾部）TreeNode x = left;while (x.right != null) {x = x.right;}// 将左子树的尾部连接到右子树x.right = right;// 当前节点的右指针指向左子树，左指针置空root.right = left;root.left = null;}}
}

题解做法：
对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。

class Solution {public void flatten(TreeNode root) {TreeNode curr = root;while (curr != null) {if (curr.left != null) {TreeNode next = curr.left;TreeNode predecessor = next;while (predecessor.right != null) {predecessor = predecessor.right;}predecessor.right = curr.right;curr.left = null;curr.right = next;}curr = curr.right;}}
}