114. Flatten Binary Tree to Linked List
給定一棵二元樹的根節點，將樹展平成一個“鏈表”：
這個“鏈表”應該使用相同的TreeNode類，其中右子指針指向鏈表中的下一個節點，左子指針始終為null。 這個“鏈表”的順序應該與二元樹的前序遍歷順序相同。
範例：
輸入：root = [1,2,5,3,4,null,6] 輸出：[1,null,2,null,3,null,4,null,5,null,6]
Python
from typing import Optional
# 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
# Initialize a stack and push the root node
stack = [root]
# Pointer to keep track of the last processed node
prev = None
while stack:
# Pop the top node from the stack
node = stack.pop()
# If there was a previous node, adjust the pointers
if prev:
prev.left = None
prev.right = node
# Push the right and then left child to the stack (so that left is processed first)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
# Update the previous node to the current node
prev = node
16.71MB, 43ms
C++
#include <stack>
using namespace std;
class Solution {
public:
void flatten(TreeNode* root) {
if (!root) {
return;
}
// Stack to help with the traversal
stack<TreeNode*> s;
s.push(root);
TreeNode* prev = nullptr;
while (!s.empty()) {
TreeNode* curr = s.top();
s.pop();
// If there was a previous node, adjust the pointers
if (prev) {
prev->left = nullptr;
prev->right = curr;
}
// Push the right and then left child to the stack
if (curr->right) {
s.push(curr->right);
}
if (curr->left) {
s.push(curr->left);
}
// Update the previous node to the current node
prev = curr;
}
}
};
15.96MB, 7ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
if (!root) {
return;
}
// Stack to help with the traversal
let stack = [];
stack.push(root);
let prev = null;
while (stack.length > 0) {
let curr = stack.pop();
// If there was a previous node, adjust the pointers
if (prev !== null) {
prev.left = null;
prev.right = curr;
}
// Push the right and then left child to the stack
if (curr.right !== null) {
stack.push(curr.right);
}
if (curr.left !== null) {
stack.push(curr.left);
}
// Update the previous node to the current node
prev = curr;
}
};
52.56MB, 57ms
