翻转二叉树

题目要求

你需要编写一个函数，该函数接收一个二叉树的根节点 root 作为参数。你的任务是将这棵二叉树进行翻转，即交换每个节点的左右子节点，然后返回翻转后的二叉树的根节点。

解题思路

翻转二叉树是一道经典的二叉树问题，可以通过递归或迭代的方式来解决。以下是解题的基本思路：

1. 递归法：

   • 检查当前节点是否为空，如果为空，则不需要进行任何操作。
   • 递归地对当前节点的左子树进行翻转。
   • 递归地对当前节点的右子树进行翻转。
   • 交换当前节点的左右子节点。
   • 最后返回当前节点（现在它已经成为了翻转后的根节点）。

2. 迭代法：

   • 使用一个栈或队列来存储所有需要交换子节点的树节点。
   • 将根节点放入栈或队列中。
   • 当栈或队列不为空时，循环执行以下操作：
     • 取出一个节点。
     • 交换这个节点的左右子节点。
     • 如果左子节点不为空，将它加入栈或队列。
     • 如果右子节点不为空，将它加入栈或队列。
   • 继续这个过程直到栈或队列为空，这时所有节点都已经翻转。
   • 返回最初放入栈或队列的根节点，它现在是翻转后的根节点。

在实际编码时，递归法的代码通常更简洁，但是迭代法在处理非常深的树时可能会有更好的性能，因为它不会受到调用栈大小的限制。

Golang 版本

package main

import "fmt"

// TreeNode is a structure for tree nodes
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// invertTree function inverts a binary tree
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // Swap the left and right children
    root.Left, root.Right = root.Right, root.Left
    // Recursively invert the left subtree
    invertTree(root.Left)
    // Recursively invert the right subtree
    invertTree(root.Right)
    return root
}

// Helper function to print the tree in-order (for verification)
func printTree(root *TreeNode) {
    if root == nil {
        return
    }
    printTree(root.Left)
    fmt.Print(root.Val, " ")
    printTree(root.Right)
}

func main() {
    // Example usage:
    // Constructing a binary tree:
    //      1
    //     / \
    //    2   3
    //   / \ / \
    //  4  5 6  7
    root := &TreeNode{1,
                      &TreeNode{2,
                                &TreeNode{4, nil, nil},
                                &TreeNode{5, nil, nil}},
                      &TreeNode{3,
                                &TreeNode{6, nil, nil},
                                &TreeNode{7, nil, nil}}}

    fmt.Println("Original tree in-order:")
    printTree(root)
    fmt.Println()

    invertedRoot := invertTree(root)

    fmt.Println("Inverted tree in-order:")
    printTree(invertedRoot)
    fmt.Println()
}

这段代码定义了一个TreeNode结构体，实现了一个invertTree函数来翻转二叉树，并提供了一个printTree辅助函数来按顺序打印树的节点值，以便验证翻转是否正确。main函数中创建了一个简单的二叉树，并展示了翻转前后的结果。

C++版本

#include <iostream>
using namespace std;

// 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:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        // Swap the left and right children
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;

        // Recursively invert the left subtree
        invertTree(root->left);
        // Recursively invert the right subtree
        invertTree(root->right);

        return root;
    }
};

// Helper function to print the tree in-order (for verification)
void printTree(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    printTree(root->left);
    cout << root->val << " ";
    printTree(root->right);
}

int main() {
    // Example usage:
    // Constructing a binary tree:
    //      1
    //     / \
    //    2   3
    //   / \ / \
    //  4  5 6  7
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    cout << "Original tree in-order: ";
    printTree(root);
    cout << endl;

    Solution solution;
    TreeNode *invertedRoot = solution.invertTree(root);

    cout << "Inverted tree in-order: ";
    printTree(invertedRoot);
    cout << endl;

    // Clean up memory if needed
    // Remember to delete the nodes of the tree to prevent memory leaks
    // This part is omitted for brevity

    return 0;
}

这段代码定义了一个TreeNode结构体和一个Solution类，其中包含了invertTree方法来翻转二叉树。还有一个printTree辅助函数用于按顺序打印树的节点值，以便验证翻转是否正确。main函数中创建了一个简单的二叉树，并展示了翻转前后的结果。注意，在实际应用中，你可能需要在程序结束前删除所有动态分配的节点，以避免内存泄漏。这部分代码在这里为了简洁而省略。

Python 版本

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        # Swap the left and right children
        root.left, root.right = root.right, root.left
        # Recursively invert the left and right subtree
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

# Helper function to print the tree in-order (for verification)
def printTree(root: TreeNode):
    if root is not None:
        printTree(root.left)
        print(root.val, end=' ')
        printTree(root.right)

# Example usage:
if __name__ == "__main__":
    # Constructing a binary tree:
    #      1
    #     / \
    #    2   3
    #   / \ / \
    #  4  5 6  7
    root = TreeNode(1,
                    TreeNode(2, TreeNode(4), TreeNode(5)),
                    TreeNode(3, TreeNode(6), TreeNode(7)))

    print("Original tree in-order:")
    printTree(root)
    print()

    solution = Solution()
    invertedRoot = solution.invertTree(root)

    print("Inverted tree in-order:")
    printTree(invertedRoot)
    print()

这段代码定义了一个TreeNode类用于表示二叉树的节点，以及一个Solution类，其中包含了invertTree方法来翻转二叉树。还有一个printTree辅助函数用于按顺序打印树的节点值，以便验证翻转是否正确。在__main__部分，创建了一个简单的二叉树，并展示了翻转前后的结果。

Java 版本

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

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // Swap the left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // Recursively invert the left and right subtree
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

// Helper function to print the tree in-order (for verification)
class BinaryTreePrinter {
    public void printTree(TreeNode root) {
        if (root != null) {
            printTree(root.left);
            System.out.print(root.val + " ");
            printTree(root.right);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        // Example usage:
        // Constructing a binary tree:
        //      1
        //     / \
        //    2   3
        //   / \ / \
        //  4  5 6  7
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        BinaryTreePrinter printer = new BinaryTreePrinter();
        System.out.print("Original tree in-order: ");
        printer.printTree(root);
        System.out.println();

        Solution solution = new Solution();
        TreeNode invertedRoot = solution.invertTree(root);

        System.out.print("Inverted tree in-order: ");
        printer.printTree(invertedRoot);
        System.out.println();
    }
}

这段代码定义了一个TreeNode类用于表示二叉树的节点，一个Solution类包含了invertTree方法来翻转二叉树，以及一个BinaryTreePrinter类包含了printTree方法用于按顺序打印树的节点值，以便验证翻转是否正确。在Main类的main方法中，创建了一个简单的二叉树，并展示了翻转前后的结果。

Rust 版本

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

// 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,
        }
    }
}

pub struct Solution {}

impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = root.clone() {
            let left = node.borrow().left.clone();
            let right = node.borrow().right.clone();
            node.borrow_mut().left = Self::invert_tree(right);
            node.borrow_mut().right = Self::invert_tree(left);
        }
        root
    }
}

fn main() {
    let 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(3))));
    let left_left = Some(Rc::new(RefCell::new(TreeNode::new(4))));
    let left_right = Some(Rc::new(RefCell::new(TreeNode::new(5))));
    let right_left = Some(Rc::new(RefCell::new(TreeNode::new(6))));
    let right_right = Some(Rc::new(RefCell::new(TreeNode::new(7))));

    if let Some(ref root_node) = root {
        root_node.borrow_mut().left = left;
        root_node.borrow_mut().right = right;
        if let Some(ref left_node) = root_node.borrow().left {
            left_node.borrow_mut().left = left_left;
            left_node.borrow_mut().right = left_right;
        }
        if let Some(ref right_node) = root_node.borrow().right {
            right_node.borrow_mut().left = right_left;
            right_node.borrow_mut().right = right_right;
        }
    }

    println!("Original tree: {:?}", root);
    let inverted_root = Solution::invert_tree(root);
    println!("Inverted tree: {:?}", inverted_root);
}

这段代码使用 Rust 语言定义了一个二叉树节点结构体TreeNode和一个解决方案结构体Solution，其中包含了invert_tree方法来翻转二叉树。在main函数中，创建了一个简单的二叉树，并展示了翻转前后的结果。Rust 版本的代码使用了Rc和RefCell来实现可变性和所有权共享，这是 Rust 语言特有的特性。

总结

上面给出了针对翻转二叉树问题的不同编程语言的解法示例。无论是使用递归还是迭代，解决方案的核心思想都是交换每个节点的左右子节点，从而实现整棵二叉树的翻转。每种语言的代码示例都展示了如何定义二叉树节点的数据结构，以及如何实现翻转二叉树的算法。这些示例为不同语言的开发者提供了参考，帮助他们理解并实现翻转二叉树的算法。