二叉树的中序遍历
题目要求
设计一个算法，实现对一棵给定的二叉树进行中序遍历，并返回遍历的结果。中序遍历的顺序是先遍历左子树，然后访问根节点，最后遍历右子树。
解题思路
中序遍历是二叉树遍历方式之一，具体的遍历步骤如下：
-
递归遍历左子树：从根节点开始，递归进入其左子节点，继续进行中序遍历，直到到达最左侧的节点。
-
访问根节点：在递归的过程中，当左子树被完全遍历后，访问当前的根节点。
-
递归遍历右子树：完成根节点的访问后，递归进入其右子节点，对右子树进行中序遍历。
这个过程可以通过递归实现，也可以通过迭代实现。递归实现较为直观，但是迭代实现可以避免递归带来的栈溢出问题，特别是在处理大型二叉树时。
递归实现的基本步骤：
-
如果当前节点为空，返回空列表（递归终止条件）。
-
递归调用左子节点，获取左子树的中序遍历结果。
-
将当前节点的值加入遍历结果列表中。
-
递归调用右子节点，获取右子树的中序遍历结果。
-
将左子树的遍历结果、当前节点值、右子树的遍历结果依次合并，返回最终的遍历结果列表。
迭代实现的基本步骤：
-
创建一个空栈和一个结果列表。
-
初始化一个指针，指向根节点。
-
当指针非空或栈非空时，执行以下操作：
a. 将指针指向的节点及其所有左子节点压入栈中，然后将指针指向最左侧节点的左子节点。
b. 当指针为空时，说明已经到达最左侧节点，此时从栈中弹出一个节点，将其值加入结果列表，并将指针指向该节点的右子节点。
c. 重复步骤 a 和 b，直到栈为空且指针为空。
-
返回结果列表，即为二叉树的中序遍历结果。
在实现时，需要注意处理好递归的终止条件以及迭代时栈的使用，确保所有节点都能按照中序遍历的顺序被访问到。
Golang 版本
package main
import "fmt"
// TreeNode is the structure for binary tree nodes
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// inorderTraversal recursively traverses the tree in inorder and returns the traversal as a slice
func inorderTraversal(root *TreeNode) []int {
var result []int
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left) // Traverse left subtree
result = append(result, node.Val) // Visit node
inorder(node.Right) // Traverse right subtree
}
inorder(root)
return result
}
func main() {
// Example usage:
// Construct a binary tree: 1
// / \
// 2 3
// / / \
// 4 5 6
root := &TreeNode{1,
&TreeNode{2,
&TreeNode{4, nil, nil},
nil},
&TreeNode{3,
&TreeNode{5, nil, nil},
&TreeNode{6, nil, nil}}}
result := inorderTraversal(root)
fmt.Println(result) // Output: [4 2 1 5 3 6]
}
这段代码定义了一个TreeNode结构体，用于构建二叉树，并实现了inorderTraversal函数，该函数接收一个二叉树的根节点，并返回一个整数切片，包含了树的中序遍历结果。在main函数中，我们构建了一个简单的二叉树，并调用inorderTraversal函数来获取和打印中序遍历的结果。
C++版本
#include <iostream>
#include <vector>
#include <stack>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
std::vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> result;
std::stack<TreeNode*> stack;
TreeNode* current = root;
while (current != nullptr || !stack.empty()) {
// Reach the left most Node of the current Node
while (current != nullptr) {
stack.push(current);
current = current->left;
}
// Current must be nullptr at this point
current = stack.top();
stack.pop();
result.push_back(current->val); // Add the node value to result
// We have visited the node and its left subtree.
// Now, it's right subtree's turn
current = current->right;
}
return result;
}
};
int main() {
// Example usage:
// Construct a binary tree: 1
// / \
// 2 3
// / / \
// 4 5 6
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->left->left = new TreeNode(4);
root->right = new TreeNode(3);
root->right->left = new TreeNode(5);
root->right->right = new TreeNode(6);
Solution solution;
std::vector<int> result = solution.inorderTraversal(root);
for (int val : result) {
std::cout << val << " ";
}
std::cout << std::endl;
// Output: 4 2 1 5 3 6
// Clean up allocated nodes
delete root->left->left;
delete root->left;
delete root->right->left;
delete root->right->right;
delete root->right;
delete root;
return 0;
}
这段 C++代码定义了一个TreeNode结构体，用于构建二叉树，并实现了一个Solution类，其中包含了inorderTraversal方法。这个方法使用了迭代的方式来进行中序遍历，利用了一个栈来存储节点。在main函数中，我们构建了一个简单的二叉树，并调用inorderTraversal方法来获取和打印中序遍历的结果。最后，代码中还包含了对动态分配的节点进行清理的步骤，以防止内存泄漏。
Python 版本
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def inorderTraversal(self, root):
result, stack = [], []
current = root
while current or stack:
# Reach the left most Node of the current Node
while current:
stack.append(current)
current = current.left
# Current must be None at this point
current = stack.pop()
result.append(current.val) # Add the node value to result
# We have visited the node and its left subtree.
# Now, it's right subtree's turn
current = current.right
return result
# Example usage:
if __name__ == "__main__":
# Construct a binary tree: 1
# / \
# 2 3
# / / \
# 4 5 6
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(4)
root.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
solution = Solution()
result = solution.inorderTraversal(root)
print(result) # Output: [4, 2, 1, 5, 3, 6]
这段 Python 代码定义了一个TreeNode类，用于构建二叉树，以及一个Solution类，其中包含了inorderTraversal方法。这个方法使用了迭代的方式来进行中序遍历，利用了一个栈来存储节点。在if __name__ == "__main__":部分，我们构建了一个简单的二叉树，并调用inorderTraversal方法来获取和打印中序遍历的结果。
Java 版本
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.val);
current = current.right;
}
return result;
}
}
public class Main {
public static void main(String[] args) {
// Example usage:
// Construct a binary tree: 1
// / \
// 2 3
// / / \
// 4 5 6
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.left = new TreeNode(4);
root.right = new TreeNode(3);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);
Solution solution = new Solution();
List<Integer> result = solution.inorderTraversal(root);
for (int val : result) {
System.out.print(val + " ");
}
// Output: 4 2 1 5 3 6
}
}
这段 Java 代码定义了一个TreeNode类，用于构建二叉树，以及一个Solution类，其中包含了inorderTraversal方法。这个方法使用了迭代的方式来进行中序遍历，利用了一个栈来存储节点。在Main类的main方法中，我们构建了一个简单的二叉树，并调用inorderTraversal方法来获取和打印中序遍历的结果。
Rust 版本
use std::cell::RefCell; use std::rc::Rc; // 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 inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> { let mut result = Vec::new(); let mut stack = Vec::new(); let mut r = root.clone(); while r.is_some() || !stack.is_empty() { while let Some(node) = r { stack.push(node.clone()); r = node.borrow().left.clone(); } r = stack.pop(); if let Some(node) = r { result.push(node.borrow().val); r = node.borrow().right.clone(); } } result } } fn main() { // Example usage: // Construct a binary tree: 1 // / \ // 2 3 // / / \ // 4 5 6 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 right_left = Some(Rc::new(RefCell::new(TreeNode::new(5)))); let right_right = Some(Rc::new(RefCell::new(TreeNode::new(6)))); 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; } if let Some(ref right_node) = root_node.borrow().right { right_node.borrow_mut().left = right_left; right_node.borrow_mut().right = right_right; } } let result = Solution::inorder_traversal(root); println!("{:?}", result); // Output: [4, 2, 1, 5, 3, 6] }
这段 Rust 代码定义了一个TreeNode结构体，用于构建二叉树，以及一个Solution结构体，其中包含了inorder_traversal方法。这个方法使用了迭代的方式来进行中序遍历，利用了一个向量作为栈来存储节点。在main函数中，我们构建了一个简单的二叉树，并调用inorder_traversal方法来获取和打印中序遍历的结果。
总结
上面给出了使用不同编程语言（包括 Golang、C++、Python、Java 和 Rust）实现二叉树中序遍历的代码示例。这些示例代码展示了如何使用递归或迭代的方式来遍历二叉树，并将遍历结果存储在一个数组或向量中。每种语言的代码都遵循了相似的逻辑：从根节点开始，先遍历左子树，然后访问根节点，最后遍历右子树。这些示例为理解和实现二叉树的中序遍历提供了参考。