LeetCode //C - 114. Flatten Binary Tree to Linked List-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 114. Flatten Binary Tree to Linked List。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

114. Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

LeetCode //C - 114. Flatten Binary Tree to Linked List,LeetCode,leetcode,c语言,算法

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

From: LeetCode
Link: 114. Flatten Binary Tree to Linked List

Solution:

Ideas：

Modified Pre-Order Traversal: Traditional pre-order traversal visits a node in the order: root, left subtree, and then right subtree. The modification here is that we’re doing it in a slightly different order: we first flatten the right subtree, then the left subtree, and finally process the current root.
Global prev Variable: This variable keeps track of the last node that we’ve visited. When we visit a new node, we’ll be linking this node to the prev node using the right pointer.
Flattening Process:

When we visit a node:
- We recursively flatten its right subtree.
- We recursively flatten its left subtree.
- We then update the current node’s right pointer to point to the prev node. This effectively appends the previously processed list to the current node.
- We set the current node’s left pointer to NULL (because we want the linked list to use the right pointers).
- Finally, we update the prev node to be the current node, as this node will be the previous node for the next node we process.

Resetting the prev Variable: Before starting the flattening process for a tree (or a subtree), we reset the prev variable to NULL. This ensures that the last node in the flattened list will correctly point to NULL instead of some node from a previous test case or a previous run.
Auxiliary Recursive Function: We’ve split the logic into two functions:文章来源地址https://www.toymoban.com/news/detail-707204.html

flatten_recursive handles the actual recursive flattening logic.
flatten is the main function that resets the prev variable and then calls the recursive function to perform the flattening.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* prev = NULL;

void flatten_recursive(struct TreeNode* root) {
    if (!root) return;

    flatten_recursive(root->right);
    flatten_recursive(root->left);

    root->right = prev;
    root->left = NULL;
    prev = root;
}

void flatten(struct TreeNode* root) {
    prev = NULL;  // Reset the prev variable
    flatten_recursive(root);
}