组合数学入门（2）：卡特兰数 卡特兰数是组合数学中最重要的数列之一。它们出现在许多表面上看起来完全不同的计数问题中，但实际上这些问题都具有相同的内在结构：平衡性、递归性以及“不交叉”约束。 在本文中，我们将介绍卡特兰数/Catalan，展示几个重要公式，并解释一些经典应用场景，特别是路径不能越过对角线的网格行走问题。 什么是卡特兰数？ 卡特兰数列如下： 第 n 个卡特兰数的一般公式为： 一个等价形式为： 这两个公式完全等价，在组合数学中都经常出现。 为什么卡特兰数很重要 卡特兰数用于计数许多具有递归结构或平衡结构的问题。它们通常出现在以下情形中： 对象必须以平衡方式构造， 路径必须保持在某个边界之内， 配对之间不能交叉， 结构可以被拆分为独立的左右部分。 因此，它们广泛出现在括号、树、网格、多边形以及栈操作等问题中。 一些重要的卡特兰公式 闭式公式 差分等价形式 递推公式 这个递推公式非常重要。它说明：如果一个规模为 n 的结构可以拆分为左侧大小为 i、右侧大小为 n-1-i 的两个部分，那么总数就是对所有可能拆分方式求和。 生成函数 渐近增长 …
这题比较有意思, 拿来分享一下: 在二叉树中, 根节点在深度0处, 并且每个深度k节点的子节点在深度k + 1处. 如果二元树的两个节点具有相同的深度但具有不同的父节点, 则它们是堂/表兄弟. 我们给出了具有唯一值的二叉树的根, 以及树中两个不同节点的值x和y. 当且仅当对应于值x和y的节点是同类时, 才返回true. 例如: 1 2 3 2和3的父母是同一个, 所以不是表兄弟(妹) 1 2 3 4 5 4和5是, 因为来自不同的父母, 并且所以树的高度是一样的. 深度优先+递归 二叉树(或者图)的一些算法大多数都可以用深度优先DFS来实现, …
操作给定的二叉树, 将其变换为源二叉树的镜像. 反转给定的二叉树 输入描述: 二叉树的镜像定义: 源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ …
题意: 找出所有左子树上的叶节点的值之和. 3 / \ 9 20 / \ 15 7 比如上面 9 和15是左子树上的子节点, 那么求和得 24. 一般来说, 遍历树有两种方式: 深度优先DFS和广度优先BFS. 解这题的关键就在需要知道叶子节点是从左边来的还是从右边来的. C++ 定义二叉树 struct TreeNode { int val; TreeNode *left; …
