一、題目大意
給你二叉樹的根結點 root ，請你將它展開為一個單鏈表：
展開后的單鏈表應該同樣使用 TreeNode ，其中 right 子指標指向鏈表中下一個結點，而左子指標始終為 null ，
展開后的單鏈表應該與二叉樹 先序遍歷 順序相同，
示例 1：
輸入：root = [1,2,5,3,4,null,6]
輸出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
輸入：root = []
輸出：[]
示例 3：
輸入：root = [0]
輸出：[0]
提示：
-
樹中結點數在范圍 [0, 2000] 內
-
-100 <= Node.val <= 100
進階：你可以使用原地演算法（O(1) 額外空間）展開這棵樹嗎？
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
思路：非迭代版實作，從根節點開始出發，先檢測其左子節點是否存在，如存在則將根節點和其右節點斷開，將左子節點及其后面所有結構一起連接到右子節點的位置，把原右子節點連到原左子節點為最后面的右子節點之后，
三、解題方法
3.1 Java實作
/**
* 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) {
// 下面再來看非迭代版本的實作，這個方法是從根節點開始出發，先檢測其左子結點是否存在，如存在則將根節點和其右子節點斷開，
// 將左子結點及其后面所有結構一起連到原右子節點的位置，把原右子節點連到元左子結點最后面的右子節點之后，代碼如下：
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode p = cur.left;
while (p.right != null) {
p = p.right;
}
p.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
}
}
四、總結小記
- 2022/9/6 按起了葫蘆起了瓢；都不愿意寫檔案，全憑個人經驗來推動
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/504724.html
標籤：其他