二叉树系列主题Code

Python实现二叉树遍历

# 定义二叉树节点类  
class TreeNode:  def __init__(self, val=0, left=None, right=None):  self.val = val  self.left = left  self.right = right  # 前序遍历（非递归）  
def preorderTraversal(root):  if not root:  return []  stack, output = [root], []  while stack:  node = stack.pop()  if node:  output.append(node.val)  if node.right:  stack.append(node.right)  if node.left:  stack.append(node.left)  return output  # 中序遍历（非递归）  
def inorderTraversal(root):  stack, output, current = [], [], root  while True:  while current:  stack.append(current)  current = current.left  if not stack:  return output  current = stack.pop()  output.append(current.val)  current = current.right  # 后序遍历（非递归）  
def postorderTraversal(root):  if not root:  return []  stack1, stack2, output = [root], [], []  while stack1:  node = stack1.pop()  if node:  stack2.append(node)  if node.left:  stack1.append(node.left)  if node.right:  stack1.append(node.right)  while stack2:  node = stack2.pop()  output.append(node.val)  return output[::-1]  # 逆序输出，得到后序遍历结果  # 层次遍历（非递归）  
def levelOrderTraversal(root):  if not root:  return []  from collections import deque  queue, output = deque([root]), []  while queue:  level_size = len(queue)  current_level = []  for _ in range(level_size):  node = queue.popleft()  # 弹出队列左侧元素  current_level.append(node.val)  if node.left:  queue.append(node.left)  # 左孩子入队  if node.right:  queue.append(node.right)  # 右孩子入队  output.append(current_level)  return output

cpp实现二叉树遍历

#include <iostream>  
#include <stack>  
#include <queue>
using namespace std;  // 二叉树节点定义  
struct TreeNode {  int val;  TreeNode* left;  TreeNode* right;  TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
};  // 前序遍历（递归实现）  
void preorderTraversalRecursive(TreeNode* root) {  if (root == NULL) {  return;  }  cout << root->val << " ";  preorderTraversalRecursive(root->left);  preorderTraversalRecursive(root->right);  
}  // 前序遍历（迭代实现）  
void preorderTraversalIterative(TreeNode* root) {  if (root == NULL) {  return;  }  stack<TreeNode*> stk;  stk.push(root);  while (!stk.empty()) {  TreeNode* node = stk.top();  stk.pop();  cout << node->val << " ";  if (node->right != NULL) {  stk.push(node->right);  }  if (node->left != NULL) {  stk.push(node->left);  }  }  
}  // 中序遍历（递归实现）  
void inorderTraversalRecursive(TreeNode* root) {  if (root == NULL) {  return;  }  inorderTraversalRecursive(root->left);  cout << root->val << " ";  inorderTraversalRecursive(root->right);  
}  // 中序遍历（迭代实现）  
void inorderTraversalIterative(TreeNode* root) {  if (root == NULL) {  return;  }  stack<TreeNode*> stk;  TreeNode* curr = root;  while (curr != NULL || !stk.empty()) {  while (curr != NULL) {  stk.push(curr);  curr = curr->left;  }  curr = stk.top();  stk.pop();  cout << curr->val << " ";  curr = curr->right;  }  
}  // 后序遍历（递归实现）  
void postorderTraversalRecursive(TreeNode* root) {  if (root == NULL) {  return;  }  postorderTraversalRecursive(root->left);  postorderTraversalRecursive(root->right);  cout << root->val << " ";  
}  // 后序遍历（迭代实现）  
void postorderTraversalIterative(TreeNode* root) {  if (root == NULL) {  return;  }  stack<TreeNode*> stk1, stk2;  stk1.push(root);  while (!stk1.empty()) {  TreeNode* node = stk1.top();  stk1.pop();  stk2.push(node);  if (node->left != NULL) {  stk1.push(node->left);  }  if (node->right != NULL) {  stk1.push(node->right);  }  }  while (!stk2.empty()) {  cout << stk2.top()->val << " ";  stk2.pop();  }  
}  // 层次遍历  
void levelOrderTraversal(TreeNode* root) {  if (root == NULL) {  return;  }  queue<TreeNode*> q;  q.push(root);  while (!q.empty()) {  int levelSize = q.size();  for (int i = 0; i < levelSize; i++) {  TreeNode* node = q.front();  q.pop();  cout << node->val << " ";  if (node->left != NULL) {  q.push(node->left);  }  if (node->right != NULL) {  q.push(node->right);  }  }  cout << endl; // 每一层遍历完后换行  }  int main() {  // 创建二叉树  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 << "前序遍历（递归实现）: ";  preorderTraversalRecursive(root); cout << endl; // 输出：1 2 4 5 3 6 7
}

水平有限，有问题随时联系~