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;}}
}