文章目錄
- 二叉樹展開為鏈表
- 解法一 : 遞回解法
- 解題思路:
- 代碼實作:
- 解法二 : 迭代解法
- 解題思路:
- 代碼實作:
- 解法三 : 前驅節點 空間復雜度O(1)
- 解題思路:
- 畫圖決議:
- 代碼實作:
二叉樹展開為鏈表
LeetCode 114 : 二叉樹展開為鏈表
描述:
給你二叉樹的根結點 root ，請你將它展開為一個單鏈表：
- 展開后的單鏈表應該同樣使用 TreeNode ，其中 right 子指標指向鏈表中下一個結點，而左子指標始終為 null ，
- 展開后的單鏈表應該與二叉樹 先序遍歷 順序相同，
解法一 : 遞回解法
解題思路:
- 使用前序遍歷的方法,添加到
list當中- 遍歷
list中的元素,讓i下標節點的左子樹為空,右子樹指向i+1下標的節點.
代碼實作:
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
preorderTraversal(root, list);
for (int i = 0; i < list.size() - 1; i++) {
list.get(i).left = null;
list.get(i).right = list.get(i+1);
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
if (root == null) return;
list.add(root);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
}
解法二 : 迭代解法
解題思路:
- 使用堆疊的后進先出的特性,記錄下前一個節點.
- 如果堆疊不為空,或者該節點不為空,進入回圈,如果該節點不為空,入堆疊,并插入到
list當中.回圈該節點的左子樹,直到為空停止回圈.- 如果左子樹為空,則出堆疊頂元素,再回圈遍歷堆疊頂節點的右子樹.
- 如果堆疊為空,并且節點也遍歷完了,就結束回圈.
- 然后再遍歷list 和 方法一的步驟一致.
代碼實作:
class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
List<TreeNode> list = new ArrayList<>();
TreeNode cur = root;
//cur 不為空 或 堆疊 不為空 進入回圈
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);//cur不為空就入堆疊
list.add(cur);//入堆疊的同時插入到list中
cur = cur.left;//根->左的順序
}
TreeNode top = stack.pop();
cur = top.right;//根->左 結束之后 就開始 右
}
//遍歷list
for (int i = 0; i < list.size() - 1; i++) {
list.get(i).left = null;
list.get(i).right = list.get(i+1);
}
}
}
解法三 : 前驅節點 空間復雜度O(1)
解題思路:
- 始終讓根節點的右子樹連接到左子樹的右子樹,讓根的左子樹變成根的右子樹,左子樹置空,然后讓root = root.right.
- 如果根節點不為空,參考
cur指向root.- 如果
root的左子樹不為空,參考一個curNext指向root.left;- 參考一個
pre指向curNext,回圈直到pre.right = null,如果pre.right != null,讓pre = pre.right. 如果回圈結束,pre.right == null. 讓pre.right = cur. right.- 讓
cur.left = null,cur.right = curNext;cur = cur.right;- 回圈 2~4 步驟.
畫圖決議:
代碼實作:
class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
TreeNode cur = root;
TreeNode curNext = null;
while (cur != null){
if(cur.left != null){
curNext = cur.left;
TreeNode pre = curNext;
//讓pre指向左子樹的最右節點
while (pre.right != null){
pre = pre.right;
}
//讓左子樹最右節點和右子樹鏈接
pre.right = cur.right;
//讓根節點的左邊斷開
cur.left = null;
//讓根節點的右子樹連接左子樹
cur.right = curNext;
}
cur = cur.right;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/395106.html
標籤：java