LeetCode114：二叉树展开为链表（三解法）
题目LeetCode114
给你二叉树的根结点root，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
Python解法
解法一（前序遍历）
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ preorderList = list() def preorder(root: TreeNode): if root: preorderList.append(root) preorder(root.left) preorder(root.right) preorder(root) size = len(preorderList) for i in range(1, size): pre, cur = preorderList[i - 1], preorderList[i] pre.left = None pre.right = cur解法二（遍历并生成）
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ if not root: return stack = [root] pre = None while stack: cur = stack.pop() if pre: pre.left = None pre.right = cur left, right = cur.left, cur.right if right: stack.append(right) if left: stack.append(left) pre = cur过程演示
解法三（前驱结点）
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ cur = root while cur: if cur.left: predecessor = cur.left while predecessor: predecessor = precedecessor.right predecessor.right = cur.right cur.right = cur.left cur.left = None cur = cur.right过程演示
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 { // 存储前序遍历所有节点 private List<TreeNode> preList = new ArrayList<>(); public void flatten(TreeNode root) { // 1. 递归前序遍历收集节点 preOrderTraverse(root); int size = preList.size(); // 2. 遍历列表，拼接成单链表 for (int i = 1; i < size; i++) { TreeNode prev = preList.get(i - 1); TreeNode curr = preList.get(i); prev.left = null; // 左指针置空 prev.right = curr; // 右指针指向下一节点 } } // 递归前序遍历：根 -> 左 -> 右 private void preOrderTraverse(TreeNode root) { if (root == null) return; preList.add(root); preOrderTraverse(root.left); preOrderTraverse(root.right); } }解法二（遍历并生成）
/** * 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) { if (root == null) return; Stack<TreeNode> stack = new Stack<>(); stack.push(root); TreeNode prev = null; // 记录上一个处理的节点 while (!stack.isEmpty()) { TreeNode curr = stack.pop(); // 上一节点指向当前节点 if (prev != null) { prev.left = null; prev.right = curr; } // 先存左右子节点，栈后进先出，先压右再压左保证前序 TreeNode left = curr.left; TreeNode right = curr.right; if (right != null) { stack.push(right); } if (left != null) { stack.push(left); } // 更新前驱节点 prev = curr; } } }解法三（前驱结点）
/** * 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 curr = root; // 逐个向右遍历节点 while (curr != null) { // 当前节点存在左子树才需要调整 if (curr.left != null) { // nxt 保存左子树头部 TreeNode nxt = curr.left; TreeNode predecessor = nxt; // 找到左子树最右侧节点 while (predecessor.right != null) { predecessor = predecessor.right; } // 左子树末尾接上原右子树 predecessor.right = curr.right; // 左子树移到右侧，清空左指针 curr.left = null; curr.right = nxt; } // 处理下一个节点 curr = curr.right; } } }C++解法
解法一（前序遍历）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private: vector<TreeNode*> preList; // 前序递归收集节点 void preOrderTraverse(TreeNode* root) { if (!root) return; preList.push_back(root); preOrderTraverse(root->left); preOrderTraverse(root->right); } public: void flatten(TreeNode* root) { preOrderTraverse(root); int size = preList.size(); // 节点串联成右斜单链表 for (int i = 1; i < size; ++i) { TreeNode* prev = preList[i - 1]; TreeNode* curr = preList[i]; prev->left = nullptr; prev->right = curr; } } };解法二（遍历并生成）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void flatten(TreeNode* root) { if (!root) return; stack<TreeNode*> stk; stk.push(root); TreeNode* prev = nullptr; while (!stk.empty()) { TreeNode* curr = stk.top(); stk.pop(); // 拼接前后节点 if (prev) { prev->left = nullptr; prev->right = curr; } // 先右后左入栈，弹出顺序为前序 TreeNode* left = curr->left; TreeNode* right = curr->right; if (right) stk.push(right); if (left) stk.push(left); prev = curr; } } };解法三（前驱结点）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void flatten(TreeNode* root) { TreeNode* curr = root; while (curr) { // 存在左子树则重构指针 if (curr->left) { TreeNode* nxt = curr->left; TreeNode* predecessor = nxt; // 遍历到左子树最右端节点 while (predecessor->right) { predecessor = predecessor->right; } // 拼接原右子树 predecessor->right = curr->right; // 左树迁移到右分支 curr->left = nullptr; curr->right = nxt; } // 向右前进 curr = curr->right; } } };