04-二叉树

💡 核心结论

二叉树本质

  • 定义：每个节点最多有两个子节点的树结构

  • 遍历：前序、中序、后序、层序，各有应用场景

  • 深度优先：递归（前中后序）或栈实现

  • 广度优先：队列实现层序遍历

  • 应用：表达式树、文件系统、DOM树

遍历方式对比

遍历

顺序

应用

实现

前序

根→左→右

复制树、序列化

递归/栈

中序

左→根→右

BST有序输出

递归/栈

后序

左→右→根

删除树、计算表达式

递归/栈

层序

逐层

打印层级、BFS

队列

关键概念

  • 满二叉树：每层都满，节点数 = 2^h - 1

  • 完全二叉树：除最后一层外都满，最后一层从左到右连续

  • 平衡二叉树：左右子树高度差 ≤ 1

  • 深度：从根到节点的边数

  • 高度：从节点到叶子的最长路径

性质

  • n个节点的二叉树高度：⌈log₂(n+1)⌉ ≤ h ≤ n

  • 第i层最多有 2^(i-1) 个节点

  • 深度为h的二叉树最多有 2^h - 1 个节点

🌳 二叉树遍历

递归遍历

def preorder(root):    # 前序：根左右
    if not root: return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

def inorder(root):     # 中序：左根右
    if not root: return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

def postorder(root):   # 后序：左右根
    if not root: return
    postorder(root.left)
    postorder(root.right)
    print(root.val)

迭代遍历（重要）

# 前序（栈）
def preorder_iterative(root):
    if not root: return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right: stack.append(node.right)
        if node.left: stack.append(node.left)
    return result

# 中序（栈）
def inorder_iterative(root):
    stack, result = [], []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

# 层序（队列）
def levelorder(root):
    if not root: return []
    queue, result = [root], []
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

🎯 常见问题

树的高度/深度

def height(root):
    if not root: return 0
    return 1 + max(height(root.left), height(root.right))

节点数

def count_nodes(root):
    if not root: return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

镜像翻转

def mirror(root):
    if not root: return
    root.left, root.right = root.right, root.left
    mirror(root.left)
    mirror(root.right)

路径和

def has_path_sum(root, target):
    if not root: return False
    if not root.left and not root.right:
        return root.val == target
    return (has_path_sum(root.left, target - root.val) or
            has_path_sum(root.right, target - root.val))

📚 LeetCode练习

💻 完整代码实现

Python 实现

  1"""
  2二叉树实现和遍历
  3"""
  4
  5class TreeNode:
  6    """二叉树节点"""
  7    
  8    def __init__(self, val=0, left=None, right=None):
  9        self.val = val
 10        self.left = left
 11        self.right = right
 12
 13
 14class BinaryTree:
 15    """二叉树"""
 16    
 17    def __init__(self):
 18        self.root = None
 19    
 20    # ========== 递归遍历 ==========
 21    
 22    def preorder(self, root):
 23        """前序遍历：根→左→右"""
 24        if not root:
 25            return []
 26        return [root.val] + self.preorder(root.left) + self.preorder(root.right)
 27    
 28    def inorder(self, root):
 29        """中序遍历：左→根→右"""
 30        if not root:
 31            return []
 32        return self.inorder(root.left) + [root.val] + self.inorder(root.right)
 33    
 34    def postorder(self, root):
 35        """后序遍历：左→右→根"""
 36        if not root:
 37            return []
 38        return self.postorder(root.left) + self.postorder(root.right) + [root.val]
 39    
 40    # ========== 迭代遍历 ==========
 41    
 42    def preorder_iterative(self, root):
 43        """前序遍历（迭代）"""
 44        if not root:
 45            return []
 46        
 47        stack, result = [root], []
 48        while stack:
 49            node = stack.pop()
 50            result.append(node.val)
 51            # 先压右子树，再压左子树（栈是后进先出）
 52            if node.right:
 53                stack.append(node.right)
 54            if node.left:
 55                stack.append(node.left)
 56        return result
 57    
 58    def inorder_iterative(self, root):
 59        """中序遍历（迭代）"""
 60        stack, result = [], []
 61        curr = root
 62        
 63        while curr or stack:
 64            # 一直往左走
 65            while curr:
 66                stack.append(curr)
 67                curr = curr.left
 68            # 处理节点
 69            curr = stack.pop()
 70            result.append(curr.val)
 71            # 转向右子树
 72            curr = curr.right
 73        
 74        return result
 75    
 76    def levelorder(self, root):
 77        """层序遍历（BFS）"""
 78        if not root:
 79            return []
 80        
 81        queue, result = [root], []
 82        while queue:
 83            node = queue.pop(0)
 84            result.append(node.val)
 85            if node.left:
 86                queue.append(node.left)
 87            if node.right:
 88                queue.append(node.right)
 89        return result
 90    
 91    def levelorder_levels(self, root):
 92        """层序遍历（分层）"""
 93        if not root:
 94            return []
 95        
 96        queue, result = [root], []
 97        while queue:
 98            level_size = len(queue)
 99            level_vals = []
100            
101            for _ in range(level_size):
102                node = queue.pop(0)
103                level_vals.append(node.val)
104                if node.left:
105                    queue.append(node.left)
106                if node.right:
107                    queue.append(node.right)
108            
109            result.append(level_vals)
110        return result
111    
112    # ========== 树的性质 ==========
113    
114    def height(self, root):
115        """树的高度"""
116        if not root:
117            return 0
118        return 1 + max(self.height(root.left), self.height(root.right))
119    
120    def count_nodes(self, root):
121        """节点数"""
122        if not root:
123            return 0
124        return 1 + self.count_nodes(root.left) + self.count_nodes(root.right)
125    
126    def is_balanced(self, root):
127        """判断是否平衡"""
128        def check(node):
129            if not node:
130                return 0, True
131            
132            left_height, left_balanced = check(node.left)
133            right_height, right_balanced = check(node.right)
134            
135            balanced = (left_balanced and right_balanced and 
136                       abs(left_height - right_height) <= 1)
137            height = 1 + max(left_height, right_height)
138            
139            return height, balanced
140        
141        return check(root)[1]
142    
143    def mirror(self, root):
144        """镜像翻转"""
145        if not root:
146            return
147        root.left, root.right = root.right, root.left
148        self.mirror(root.left)
149        self.mirror(root.right)
150    
151    def max_path_sum(self, root):
152        """最大路径和"""
153        self.max_sum = float('-inf')
154        
155        def helper(node):
156            if not node:
157                return 0
158            
159            left = max(0, helper(node.left))
160            right = max(0, helper(node.right))
161            
162            # 更新最大路径和
163            self.max_sum = max(self.max_sum, node.val + left + right)
164            
165            # 返回经过当前节点的最大单边路径
166            return node.val + max(left, right)
167        
168        helper(root)
169        return self.max_sum
170
171
172def demo():
173    """演示二叉树操作"""
174    print("=== 二叉树演示 ===\n")
175    
176    # 构建树
177    #       1
178    #      / \
179    #     2   3
180    #    / \
181    #   4   5
182    
183    root = TreeNode(1)
184    root.left = TreeNode(2)
185    root.right = TreeNode(3)
186    root.left.left = TreeNode(4)
187    root.left.right = TreeNode(5)
188    
189    tree = BinaryTree()
190    tree.root = root
191    
192    # 遍历
193    print("前序遍历（递归）:", tree.preorder(root))
194    print("前序遍历（迭代）:", tree.preorder_iterative(root))
195    print()
196    
197    print("中序遍历（递归）:", tree.inorder(root))
198    print("中序遍历（迭代）:", tree.inorder_iterative(root))
199    print()
200    
201    print("后序遍历（递归）:", tree.postorder(root))
202    print()
203    
204    print("层序遍历:", tree.levelorder(root))
205    print("层序遍历（分层）:", tree.levelorder_levels(root))
206    print()
207    
208    # 性质
209    print(f"树的高度: {tree.height(root)}")
210    print(f"节点数: {tree.count_nodes(root)}")
211    print(f"是否平衡: {tree.is_balanced(root)}")
212
213
214if __name__ == '__main__':
215    demo()
216

C++ 实现

  1/**
  2 * 二叉树实现和遍历
  3 */
  4
  5#include <iostream>
  6#include <vector>
  7#include <stack>
  8#include <queue>
  9
 10struct TreeNode {
 11    int val;
 12    TreeNode* left;
 13    TreeNode* right;
 14    
 15    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
 16};
 17
 18
 19class BinaryTree {
 20public:
 21    TreeNode* root;
 22    
 23    BinaryTree() : root(nullptr) {}
 24    
 25    // ========== 递归遍历 ==========
 26    
 27    void preorder(TreeNode* node, std::vector<int>& result) {
 28        if (!node) return;
 29        result.push_back(node->val);
 30        preorder(node->left, result);
 31        preorder(node->right, result);
 32    }
 33    
 34    void inorder(TreeNode* node, std::vector<int>& result) {
 35        if (!node) return;
 36        inorder(node->left, result);
 37        result.push_back(node->val);
 38        inorder(node->right, result);
 39    }
 40    
 41    void postorder(TreeNode* node, std::vector<int>& result) {
 42        if (!node) return;
 43        postorder(node->left, result);
 44        postorder(node->right, result);
 45        result.push_back(node->val);
 46    }
 47    
 48    // ========== 迭代遍历 ==========
 49    
 50    std::vector<int> preorderIterative(TreeNode* root) {
 51        std::vector<int> result;
 52        if (!root) return result;
 53        
 54        std::stack<TreeNode*> st;
 55        st.push(root);
 56        
 57        while (!st.empty()) {
 58            TreeNode* node = st.top();
 59            st.pop();
 60            result.push_back(node->val);
 61            
 62            if (node->right) st.push(node->right);
 63            if (node->left) st.push(node->left);
 64        }
 65        
 66        return result;
 67    }
 68    
 69    std::vector<int> inorderIterative(TreeNode* root) {
 70        std::vector<int> result;
 71        std::stack<TreeNode*> st;
 72        TreeNode* curr = root;
 73        
 74        while (curr || !st.empty()) {
 75            while (curr) {
 76                st.push(curr);
 77                curr = curr->left;
 78            }
 79            curr = st.top();
 80            st.pop();
 81            result.push_back(curr->val);
 82            curr = curr->right;
 83        }
 84        
 85        return result;
 86    }
 87    
 88    std::vector<int> levelorder(TreeNode* root) {
 89        std::vector<int> result;
 90        if (!root) return result;
 91        
 92        std::queue<TreeNode*> q;
 93        q.push(root);
 94        
 95        while (!q.empty()) {
 96            TreeNode* node = q.front();
 97            q.pop();
 98            result.push_back(node->val);
 99            
100            if (node->left) q.push(node->left);
101            if (node->right) q.push(node->right);
102        }
103        
104        return result;
105    }
106    
107    // ========== 树的性质 ==========
108    
109    int height(TreeNode* node) {
110        if (!node) return 0;
111        return 1 + std::max(height(node->left), height(node->right));
112    }
113    
114    int countNodes(TreeNode* node) {
115        if (!node) return 0;
116        return 1 + countNodes(node->left) + countNodes(node->right);
117    }
118    
119    void mirror(TreeNode* node) {
120        if (!node) return;
121        std::swap(node->left, node->right);
122        mirror(node->left);
123        mirror(node->right);
124    }
125    
126    // ========== 打印 ==========
127    
128    void printVector(const std::vector<int>& vec) {
129        std::cout << "[";
130        for (size_t i = 0; i < vec.size(); i++) {
131            std::cout << vec[i];
132            if (i < vec.size() - 1) std::cout << ", ";
133        }
134        std::cout << "]" << std::endl;
135    }
136    
137    ~BinaryTree() {
138        deleteTree(root);
139    }
140    
141    void deleteTree(TreeNode* node) {
142        if (node) {
143            deleteTree(node->left);
144            deleteTree(node->right);
145            delete node;
146        }
147    }
148};
149
150
151int main() {
152    std::cout << "=== 二叉树演示 ===" << std::endl << std::endl;
153    
154    // 构建树
155    //       1
156    //      / \
157    //     2   3
158    //    / \
159    //   4   5
160    
161    BinaryTree tree;
162    tree.root = new TreeNode(1);
163    tree.root->left = new TreeNode(2);
164    tree.root->right = new TreeNode(3);
165    tree.root->left->left = new TreeNode(4);
166    tree.root->left->right = new TreeNode(5);
167    
168    // 遍历
169    std::vector<int> result;
170    
171    tree.preorder(tree.root, result);
172    std::cout << "前序遍历（递归）: ";
173    tree.printVector(result);
174    
175    std::cout << "前序遍历（迭代）: ";
176    tree.printVector(tree.preorderIterative(tree.root));
177    std::cout << std::endl;
178    
179    result.clear();
180    tree.inorder(tree.root, result);
181    std::cout << "中序遍历（递归）: ";
182    tree.printVector(result);
183    
184    std::cout << "中序遍历（迭代）: ";
185    tree.printVector(tree.inorderIterative(tree.root));
186    std::cout << std::endl;
187    
188    result.clear();
189    tree.postorder(tree.root, result);
190    std::cout << "后序遍历（递归）: ";
191    tree.printVector(result);
192    std::cout << std::endl;
193    
194    std::cout << "层序遍历: ";
195    tree.printVector(tree.levelorder(tree.root));
196    std::cout << std::endl;
197    
198    // 性质
199    std::cout << "树的高度: " << tree.height(tree.root) << std::endl;
200    std::cout << "节点数: " << tree.countNodes(tree.root) << std::endl;
201    
202    return 0;
203}