[Leetcode][二叉树]相关题目汇总，分析，总结

题目汇总

以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。

目前范围：Leetcode前150题

生成二叉树

• Construct Binary Tree from Preorder and Inorder Traversal (Inorder and Postorder)
  根据二叉树的前序遍历和中序遍历（中序和后序）结果生成二叉树
  递归

• Convert Sorted Array to Binary Search Tree
  将一个排序好的数组转换为一颗二叉查找树，这颗二叉查找树要求是平衡的。
  Convert Sorted List to Binary Search Tree
  将一个排序好的链表转换为一颗二叉查找树，这颗二叉查找树要求是平衡的。
  递归

• Unique Binary Search Trees
  给定一个数n，求1-n这n个数能生成多少个二叉查找树
  动态规划
  卡特兰数（组合数学）

• Unique Binary Search Trees II
  给出一个n，求1-n能够得到的所有二叉搜索树，输出所有树
  递归
  较难

遍历二叉树

• Binary Tree Preorder Traversal
  前序遍历一个二叉树
  递归、迭代

• Binary Tree Inorder Traversal
  中序遍历一个二叉树
  递归、迭代

• Binary Tree Inorder Traversal
  后序遍历一个二叉树
  递归、迭代

前中后三种序列，递归都是一样的理解。迭代的话，前后两个可以互相理解。中序需要单独理解。当然我认为可能我还没有理解透彻。

• Binary Tree Level Order Traversal
  层序遍历，每一层上的数据按照从左到右的顺序排列。
  递归、迭代

• Binary Tree Level Order Traversal II
  层序遍历，这次是从最下层输出到根节点
  递归、迭代

• Binary Tree Zigzag Level Order Traversal
  按之字形遍历二叉树（一正一反）
  递归、迭代

这三题都是层序遍历，没有什么特别大的区别。层序遍历基本都这样，举一反三。

• Path Sum
  给定一个数和一棵树，求能否有一条路径上所有叶子结点数值加起来等于给定的数
  递归

• Path Sum II
  将根到叶子的路径和为sum的路径都枚举出来。
  递归

第二题只不过是第一题得所有可能性保存到一个数组去。

其他题目

• Maximum Depth of Binary Tree
  求二叉树最大深度
  递归 DFS

• Minimum Depth of Binary Tree
  求二叉树最小深度
  递归 DFS

• Validate Binary Search Tree
  判断一棵树是否为二叉搜索树
  递归

• Recover Binary Search Tree
  一颗二叉查找树中的某两个节点被错误的交换了，需要恢复成原来的正确的二叉查找树。
  递归

• Same Tree
  判断两颗二叉树是否完全相同
  递归

• Symmetric Tree
  判断一个树是否左右对称
  递归、迭代

上面两题类似

• Balanced Binary Tree
  判断一颗二叉树是否是“高度”平衡的。
  平衡二叉树的定义是二叉树的任意节点的两颗子树之间的高度差小于等于1。
  递归

• Flatten Binary Tree to Linked List 难题
  把一棵二叉树变为链表（扁平化）
  迭代

• Sum Root to Leaf Numbers
  要求所有从根节点到叶子节点组成的数字的和。
  递归

• Binary Tree Maximum Path Sum
  求一棵二叉树中最大的路径和。
  递归

• Populating Next Right Pointers in Each Node I and II
  为二叉树的节点都添加一个next指针，指向跟它在同一高度的右边的节点，如果右边没有节点，就指向None。
  迭代、递归

二叉树总结

• leetcode的测试集经常会有[], [0]，所以很多题目先要考虑判断是否为空，return None或者return []。

• 递归和迭代
  递归中必有迭代，迭代未必用到递归
  （递归（浪费资源反复调用函数）> 迭代）
  迭代——《明日边缘》
  递归——《盗梦空间》
  递归是一个树结构，每个分支都探究到最远，发现无法继续的时候往回走，每个节点只会访问一次
  迭代是一个环结构，每次迭代都是一个圈，不会拉掉其中的某一步，然后不断循环，每个节点都会被循环访问

• 二叉树在python中用法
  root.val是该节点的值。
  root则相当于指向该节点的指针。
  root.left, root.right指向其左右节点的位置