二叉树展开为链表

题目要求

给定一个二叉树的根节点 root，要求将这棵二叉树原地展开为一个单链表。这里的“原地”意味着不能使用额外的数据结构，只能通过修改原二叉树节点的指针来实现。展开规则如下：

展开后的单链表使用原二叉树的 TreeNode 结构，每个节点的 right 指针指向链表中的下一个节点，而每个节点的 left 指针必须指向 null。
展开后的单链表中节点的顺序应该与原二叉树的先序遍历（根-左-右）顺序相同。

解题思路

要将二叉树展开为一个单链表，并且要求展开后的顺序与先序遍历相同，我们可以按照以下步骤来实现：

先序遍历的模拟：我们可以模拟先序遍历的过程，这个过程中我们会访问每个节点。在访问的同时，我们可以修改节点的指针来达到展开的目的。
节点处理：对于每个节点，我们需要做的是：
- 将当前节点的左子树插入到当前节点和右子树之间。
- 将当前节点的左子树设置为 null。
- 将原来的右子树接到当前左子树的最右边的节点上。
递归或迭代：这个过程可以通过递归或迭代的方式完成。递归的话，我们可以先递归处理左子树，然后递归处理右子树，最后进行节点的连接。迭代的话，我们可以使用栈来模拟递归过程。
原地操作：由于题目要求原地展开，我们不能创建新的节点，只能修改现有节点的指针。
细节处理：在实际操作中，我们需要注意：
- 在连接节点时，要考虑左子树为空的情况。
- 在找左子树最右边的节点时，要考虑左子树可能已经是一个展开的链表的情况。

通过以上步骤，我们可以将二叉树原地展开为一个单链表，且满足先序遍历的顺序。

Golang 版本

package main

// TreeNode is the definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func flatten(root *TreeNode)  {
    // curr points to the current node being processed
    curr := root
    for curr != nil {
        if curr.Left != nil {
            // Find the rightmost node of the left subtree
            prev := curr.Left
            for prev.Right != nil {
                prev = prev.Right
            }
            // Make the rightmost node of the left subtree point to the current right subtree
            prev.Right = curr.Right
            // Move the left subtree to the right, effectively flattening the left part
            curr.Right = curr.Left
            curr.Left = nil
        }
        // Move on to the right side of the tree
        curr = curr.Right
    }
}

func main() {
    // Example usage:
    // Construct the binary tree here and call flatten(root)
}

这段代码定义了一个TreeNode结构体，代表二叉树的节点，并实现了flatten函数，该函数接受一个二叉树的根节点，并原地将其展开为一个单链表。主要逻辑在于遍历每个节点，如果当前节点有左子树，则找到左子树的最右节点，将当前节点的右子树接到该最右节点的右指针上，然后将左子树移到右边，左指针置为nil。然后继续处理当前节点的右子树，直到所有节点都被处理完毕。

C++版本

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;

        TreeNode* node = root;
        while (node) {
            if (node->left) {
                // Find the rightmost node of the left subtree
                TreeNode* rightmost = node->left;
                while (rightmost->right) {
                    rightmost = rightmost->right;
                }
                // Connect the rightmost node of the left subtree with the right subtree
                rightmost->right = node->right;
                // Move the left subtree to the right
                node->right = node->left;
                node->left = nullptr;
            }
            // Move to the right side of the tree
            node = node->right;
        }
    }
};

int main() {
    // Example usage:
    // TreeNode* root = new TreeNode(1);
    // root->left = new TreeNode(2);
    // root->right = new TreeNode(5);
    // ...
    // Solution().flatten(root);
    // The tree should now be flattened
    return 0;
}

这段 C++代码定义了一个二叉树节点结构体TreeNode和一个解决方案类Solution。Solution类中的flatten函数接受一个二叉树的根节点，并原地将其展开为一个单链表。函数的主体是一个循环，遍历每个节点，如果当前节点有左子树，则找到左子树的最右节点，并将当前节点的右子树接到该最右节点的右指针上。然后将左子树移到右边，左指针置为nullptr。之后继续处理当前节点的右子树，直到所有节点都被处理完毕。在main函数中，你可以根据需要构造二叉树，并调用flatten函数来展平它。

Python 版本

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: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # Start with the root node
        current = root
        while current:
            if current.left:
                # Find the rightmost node of the left subtree
                rightmost = current.left
                while rightmost.right:
                    rightmost = rightmost.right
                # Connect the rightmost node of the left subtree with the right subtree
                rightmost.right = current.right
                # Move the left subtree to the right
                current.right = current.left
                current.left = None
            # Move to the right side of the tree
            current = current.right

# Example usage:
# if __name__ == "__main__":
#     root = TreeNode(1)
#     root.left = TreeNode(2)
#     root.right = TreeNode(5)
#     root.left.left = TreeNode(3)
#     root.left.right = TreeNode(4)
#     root.right.right = TreeNode(6)
#     Solution().flatten(root)
#     # Now the tree is flattened

这段 Python 代码定义了一个二叉树节点类TreeNode和一个解决方案类Solution。Solution类中的flatten方法接受一个二叉树的根节点，并原地将其展开为一个单链表。方法的主体是一个循环，遍历每个节点，如果当前节点有左子树，则找到左子树的最右节点，并将当前节点的右子树接到该最右节点的右指针上。然后将左子树移到右边，左指针置为None。之后继续处理当前节点的右子树，直到所有节点都被处理完毕。在if __name__ == "__main__":部分，你可以构造一个二叉树，并调用flatten方法来展平它。

Java 版本

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public void flatten(TreeNode root) {
        TreeNode current = root;
        while (current != null) {
            if (current.left != null) {
                // Find the rightmost node of the left subtree
                TreeNode rightmost = current.left;
                while (rightmost.right != null) {
                    rightmost = rightmost.right;
                }
                // Connect the rightmost node of the left subtree with the right subtree
                rightmost.right = current.right;
                // Move the left subtree to the right
                current.right = current.left;
                current.left = null;
            }
            // Move to the right side of the tree
            current = current.right;
        }
    }
}

// Example usage:
// public static void main(String[] args) {
//     Solution solution = new Solution();
//     TreeNode root = new TreeNode(1);
//     root.left = new TreeNode(2);
//     root.right = new TreeNode(5);
//     root.left.left = new TreeNode(3);
//     root.left.right = new TreeNode(4);
//     root.right.right = new TreeNode(6);
//     solution.flatten(root);
//     // Now the tree is flattened
// }

这段 Java 代码定义了一个二叉树节点类TreeNode和一个解决方案类Solution。Solution类中的flatten方法接受一个二叉树的根节点，并原地将其展开为一个单链表。方法的主体是一个循环，遍历每个节点，如果当前节点有左子树，则找到左子树的最右节点，并将当前节点的右子树接到该最右节点的右指针上。然后将左子树移到右边，左指针置为null。之后继续处理当前节点的右子树，直到所有节点都被处理完毕。在main方法中，你可以构造一个二叉树，并调用flatten方法来展平它。

Rust 版本

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

use std::rc::Rc;
use std::cell::RefCell;

pub struct Solution {}

impl Solution {
    pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
        let mut current = root.clone();
        while let Some(node) = current {
            let mut node_borrowed = node.borrow_mut();
            if let Some(left) = node_borrowed.left.take() {
                let mut rightmost = left.clone();
                // Find the rightmost node of the left subtree
                while let Some(right) = rightmost.borrow().right.clone() {
                    rightmost = right;
                }
                // Connect the rightmost node of the left subtree with the right subtree
                rightmost.borrow_mut().right = node_borrowed.right.take();
                // Move the left subtree to the right
                node_borrowed.right = Some(left);
            }
            current = node_borrowed.right.clone();
        }
    }
}

// Example usage:
// fn main() {
//     let mut root = Some(Rc::new(RefCell::new(TreeNode::new(1))));
//     let left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
//     let right = Some(Rc::new(RefCell::new(TreeNode::new(5))));
//     root.as_mut().unwrap().borrow_mut().left = left;
//     root.as_mut().unwrap().borrow_mut().right = right;
//     Solution::flatten(&mut root);
//     // Now the tree is flattened
// }

这段 Rust 代码定义了一个二叉树节点结构体TreeNode和一个解决方案结构体Solution。Solution结构体中的flatten方法接受一个可变引用到一个Option<Rc<RefCell<TreeNode>>>，这是 Rust 中常用的方式来共享可变引用。方法的主体是一个循环，遍历每个节点，如果当前节点有左子树，则找到左子树的最右节点，并将当前节点的右子树接到该最右节点的右指针上。然后将左子树移到右边，左指针置为None。之后继续处理当前节点的右子树，直到所有节点都被处理完毕。在main函数中，你可以构造一个二叉树，并调用flatten方法来展平它。

总结

上述 Rust 版本的解法采用了递归展平二叉树的方法。这种方法的核心思想是将二叉树的左子树和右子树分别展平，然后将左子树作为右子树，原右子树接到展平后的左子树的最右侧节点。这样的操作顺序符合二叉树的先序遍历（根-左-右）。

解法步骤：

对当前节点，如果存在左子树，找到左子树的最右侧节点。
将当前节点的右子树接到找到的最右侧节点的右指针上。
将当前节点的左子树置为 None，并将左子树接到当前节点的右指针上。
移动到下一个右子节点，重复步骤 1-3，直到遍历完所有节点。

编码易错点：

所有权与借用：在 Rust 中，正确处理所有权和借用是非常关键的。在操作树的节点时，需要确保使用Rc和RefCell来正确管理引用计数和内部可变性。
循环引用：在树的转换过程中，需要注意不要创建循环引用，否则会导致内存泄漏。
Option 的处理：在 Rust 中，节点可能是Some或None。在处理这些Option值时，需要使用if let或while let来正确地解构Some值，并在节点为None时跳过操作。
可变借用规则：在同一时间，你只能拥有一个可变引用或任意数量的不可变引用之一。在flatten函数中，需要小心地处理可变引用，避免同时存在多个可变引用。
递归与迭代：虽然这个问题可以用递归解决，但上述解法使用了迭代。在实现时，要注意迭代和递归的选择，以及它们在栈空间上的影响。
节点连接错误：在将左子树的最右侧节点连接到原右子树时，需要确保不会丢失原右子树的引用。
修改后继续使用旧引用：在修改树的结构后，之前的引用可能不再有效。需要确保在修改树结构后使用最新的引用。

正确处理这些易错点是实现一个无 bug 的 Rust 程序的关键。在实际编码时，应该通过编译器的所有权检查和借用检查来确保代码的正确性。此外，单元测试和集成测试也是确保代码质量的重要手段。

hot-100