【数据结构与算法】二叉树总结2

二叉树全攻略从建树到常见题型解析二叉树是算法与数据结构中最基础又最重要的内容很多面试题和竞赛题都涉及到树结构的操作。本文将从建树、遍历、BST、路径问题到树变形结合代码和示例帮助你系统掌握二叉树。一、二叉树建树建树是所有树题的基础。常见的题目是通过前序中序或中序后序构建二叉树。例如通过前序和中序TreeNode* buildTree(vectorint pre, vectorint in, int preL, int preR, int inL, int inR){ if(preL preR) return nullptr; int rootVal pre[preL]; int k find(in.begin()inL, in.begin()inR1, rootVal) - in.begin(); TreeNode* root new TreeNode(rootVal); int leftSize k - inL; root-left buildTree(pre, in, preL1, preLleftSize, inL, k-1); root-right buildTree(pre, in, preLleftSize1, preR, k1, inR); return root; }建树核心点前序第一个是根找到根在中序中的位置划分左右子树递归构建二、遍历方法遍历是操作树的核心。主要有两类1. DFS 递归void dfs(TreeNode* root){ if(!root) return; // 前序访问根节点 dfs(root-left); // 左 // 中序访问根节点 dfs(root-right); // 右 // 后序访问根节点 }2. BFS 层序vectorvectorint levelOrder(TreeNode* root){ vectorvectorint res; if(!root) return res; queueTreeNode* q; q.push(root); while(!q.empty()){ int sz q.size(); vectorint level; for(int i0;isz;i){ TreeNode* node q.front(); q.pop(); level.push_back(node-val); if(node-left) q.push(node-left); if(node-right) q.push(node-right); } res.push_back(level); } return res; }层序遍历常用于右视图、逐层打印、宽度问题。三、二叉搜索树BSTBST 有一个重要特性左 根 右。验证 BSTbool isValidBST(TreeNode* root, long minVal, long maxVal){ if(!root) return true; if(root-val minVal || root-val maxVal) return false; return isValidBST(root-left,minVal,root-val) isValidBST(root-right,root-val,maxVal); }第 k 小元素利用中序遍历有序性质void inorder(TreeNode* root, int k, int res){ if(!root) return; inorder(root-left,k,res); k--; if(k0) { resroot-val; return; } inorder(root-right,k,res); }四、路径类问题根到叶子路径和bool hasPathSum(TreeNode* root, int sum){ if(!root) return false; if(!root-left !root-right) return root-valsum; return hasPathSum(root-left,sum-root-val) || hasPathSum(root-right,sum-root-val); }最大路径和int maxPathSum(TreeNode* root, int maxSum){ if(!root) return 0; int left max(0,maxPathSum(root-left,maxSum)); int right max(0,maxPathSum(root-right,maxSum)); maxSum max(maxSum, leftrightroot-val); return root-val max(left,right); }路径问题核心是递归返回子树信息并组合。五、树变形与特殊操作翻转二叉树左右子树交换TreeNode* invertTree(TreeNode* root){ if(!root) return nullptr; swap(root-left, root-right); invertTree(root-left); invertTree(root-right); return root; }右视图每层最右节点BFS 取每层最后一个DFS 先右后左取每层第一个。展开为链表前序遍历 左右子树操作六、复杂度分析遍历类O(n) 时间O(h) 空间建树O(n²)找根在中序或 O(n) 哈希优化BST 操作O(h) ~ O(log n)