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

二叉树 20 道经典题一篇讲透所有套路附完整代码示例二叉树是算法学习中最核心的数据结构之一它几乎贯穿了结构理解、递归、动态规划、搜索和路径问题的各个方面。如果你想在算法面试或者竞赛中拔高二叉树的题型必须彻底掌握。本篇文章将通过 20 道经典题帮你建立一套完整的二叉树解题思路体系。一、建树问题题目 1前序 中序建树核心思路前序第一个节点是根在中序中找到根划分左右子树递归构建左右子树示例代码TreeNode* buildTree(string preorder, string inorder, unordered_mapchar,int mp, int preStart, int inStart, int inEnd) { if (preStart preorder.size() || inStart inEnd) return nullptr; char rootVal preorder[preStart]; TreeNode* root new TreeNode(rootVal); int pos mp[rootVal]; root-left buildTree(preorder, inorder, mp, preStart1, inStart, pos-1); root-right buildTree(preorder, inorder, mp, preStartpos-inStart1, pos1, inEnd); return root; }题目 2中序 后序建树核心与前序类似只是根节点是后序的最后一个。二、遍历套路题目 3前序遍历void preorder(TreeNode* root) { if (!root) return; cout root-val; preorder(root-left); preorder(root-right); }题目 4中序遍历void inorder(TreeNode* root) { if (!root) return; inorder(root-left); cout root-val; inorder(root-right); }题目 5后序遍历void postorder(TreeNode* root) { if (!root) return; postorder(root-left); postorder(root-right); cout root-val; }题目 6层序遍历BFSvectorvectorint 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 i 0; i sz; 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; }三、树的变形问题题目 7翻转二叉树TreeNode* invertTree(TreeNode* root) { if (!root) return nullptr; swap(root-left, root-right); invertTree(root-left); invertTree(root-right); return root; }题目 8对称二叉树bool isSymmetric(TreeNode* root) { if (!root) return true; return isMirror(root-left, root-right); } bool isMirror(TreeNode* t1, TreeNode* t2) { if (!t1 !t2) return true; if (!t1 || !t2) return false; return (t1-valt2-val) isMirror(t1-left, t2-right) isMirror(t1-right, t2-left); }题目 9右视图vectorint rightSideView(TreeNode* root) { vectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int sz q.size(); for (int i 0; i sz; i) { TreeNode* node q.front(); q.pop(); if (i sz-1) res.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } } return res; }题目 10最大路径和int maxPathSum(TreeNode* root) { int max_sum INT_MIN; functionint(TreeNode*) dfs [](TreeNode* node){ if(!node) return 0; int left max(0, dfs(node-left)); int right max(0, dfs(node-right)); max_sum max(max_sum, leftrightnode-val); return node-val max(left, right); }; dfs(root); return max_sum; }四、二叉搜索树特有题题目 11验证 BSTbool isValidBST(TreeNode* root) { return helper(root, LONG_MIN, LONG_MAX); } bool helper(TreeNode* node, long min_val, long max_val){ if(!node) return true; if(node-valmin_val || node-valmax_val) return false; return helper(node-left,min_val,node-val) helper(node-right,node-val,max_val); }题目 12第 k 小元素int kthSmallest(TreeNode* root, int k) { int count0, result0; functionvoid(TreeNode*) inorder [](TreeNode* node){ if(!node) return; inorder(node-left); count; if(countk) { resultnode-val; return; } inorder(node-right); }; inorder(root); return result; }题目 13最小高度 BST有序数组建树TreeNode* sortedArrayToBST(vectorint nums, int l, int r) { if(lr) return nullptr; int mid l (r-l)/2; TreeNode* root new TreeNode(nums[mid]); root-left sortedArrayToBST(nums,l,mid-1); root-right sortedArrayToBST(nums,mid1,r); return root; }五、树的路径类问题题目 14路径总和判断是否存在根到叶子节点路径和等于 targetbool 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); }题目 15所有路径void dfs(TreeNode* root,int sum,vectorint path, vectorvectorint res){ if(!root) return; path.push_back(root-val); if(!root-left !root-right) res.push_back(path); dfs(root-left,sum,path,res); dfs(root-right,sum,path,res); path.pop_back(); }六、特殊树形操作题目 16展开二叉树为链表void flatten(TreeNode* root) { TreeNode* noderoot; while(node){ if(node-left){ TreeNode* prenode-left; while(pre-right) prepre-right; pre-rightnode-right; node-rightnode-left; node-leftnullptr; } nodenode-right; } }题目 17左右子树交换镜像与翻转二叉树一致题目 18子树判断bool isSubtree(TreeNode* s, TreeNode* t) { if(!s) return false; return isSameTree(s,t) || isSubtree(s-left,t) || isSubtree(s-right,t); } bool isSameTree(TreeNode* a, TreeNode* b){ if(!a !b) return true; if(!a || !b) return false; if(a-val ! b-val) return false; return isSameTree(a-left,b-left) isSameTree(a-right,b-right); }题目 19统计二叉树节点数int countNodes(TreeNode* root) { if(!root) return 0; return 1countNodes(root-left)countNodes(root-right); }题目 20最大深度 / 最小深度int maxDepth(TreeNode* root){ if(!root) return 0; return 1max(maxDepth(root-left),maxDepth(root-right)); } int minDepth(TreeNode* root){ if(!root) return 0; return 1min(minDepth(root-left),minDepth(root-right)); }七、总结通过以上 20 道题你可以看到建树是所有树题的基础遍历是信息获取和递归的核心BST 的特性能大幅简化搜索类问题路径类和动态规划类题目本质是对子树结果进行组合特殊操作题往往是遍历 小技巧