【二叉树的中序遍历】为什么叫中序根节点被访问的位置。前序根 - 左 - 右中序左 - 根 - 右后序左 - 右 - 根【二叉树的最大深度】dfs 递归算法节点为空判断一波max进入左节点时depth 退出 遍历完右节点 depth--【翻转二叉树】递归翻转交换左右节点root.Left, root.Right invert(root.Right), invert(root.Left)【对称二叉树】使用mirror函数递归比较 a节点的左叶子和b节点的右叶子a节点的右叶子和b节点的左叶子。另外当anil bnil 说明对称【二叉树的直径】后序递归遍历子节点对于每个节点它的最大直径为左子树高度右子树高度-1然后向父亲节点返回当前节点的高度【二叉树的层序遍历】用一个临时数组roots1保存当前层的节点遍历数组记录值然后将其叶子节点加入到数组root2。然后下一轮遍历root2【将有序数组转换为二叉搜索树】每次选择有序数组中间的那个数字作为根节点这样一定能保证左右子树高度相差1然后递归处理有序数组每次拆成除中间元素外左右两个数组。【98. 验证二叉搜索树】对于每个节点值检查一定要传入其祖先节点所有值构成的上下界而不只是根据父亲节点的值判断【230. 二叉搜索树中第 K 小的元素】二叉树的特性中序遍历一定是升序的索引中序遍历遍历个节点 k-- 等于0的时候就找到了【199. 二叉树的右视图】用一个全局变量记录全局扫描历史达到最深深度然后递归扫描函数内维护一个当前扫描节点所在行数。递归扫描函数内遍历顺序需要时 根-右-左\【114. 二叉树展开为链表】如果是用递归那么空间复杂度肯定是O(n)了时间复杂度为O(1)的方法对每个节点找到左子树的最右节点也就是左子树展开链表后的尾部然后再将原右子树插入到左子树的最右节点。左子树替换原右子树的位置。