Leetcode-二叉树

https://github.com/LongxingTan/Machine-learning-interview

由于平时喜欢用LGB做数据挖掘，所以就先从二叉树开始熟悉一下leetcode。本文总结一下leetcode的二叉树类型

• https://leetcode.com/tag/binary-tree/

方法

• 有时候可以试一下递归和非递归方法，递归转化为非递归需要手工保存一个栈
• 二叉搜索树利用其特点中序遍历是排序的
• 任何题目还是要从简单或暴力解法做起

模版

• 单root
• 双root

树的遍历

主要是前中后、层序遍历

树的生成/构建

此类题目返回的是一棵树。构建时需要先构建root，再left 和right。
那么构建linked list的题目其实就是构建node和next。但是在已有树时，可以从tail或top

典型题目从preorder和inorder恢复二叉树等。

• 106. Construct Binary Tree from Inorder and Postorder Traversal

106中，虽然注意了递归。也要却要注意先生成右子树，再生成左子树的顺序，否则报错节点不存在。因为写法里有关于后续的pop，只有右子树的pop完之后剩下的才都是左子树节点

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder or not postorder:
            return        
 
        root = TreeNode(postorder.pop(-1))
        index = inorder.index(root.val)
        root.right = self.buildTree(inorder[index+1:], postorder)
        root.left = self.buildTree(inorder[: index], postorder)
        
        return root
1
2
3
4
5
6
7
8
9
10
11

• 105. Construct Binary Tree from Preorder and Inorder Traversal

• Unique Binary Search Trees II

这题还是很综合的，有树的构建、有BST、还有类似回溯的permuattion。

• 108 https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
  根据审题可知，要构建一颗高度平衡的BST。所以就要利用性质，而且构建树的时候都要先构建root其实，再利用BST的性质找到root，也就是中位数。

• 109 https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
  和108思路类似，构建树需要先从root开始，然后左右。而bst的root是中位数，array可以直接根据位置得到，list则可以根据快慢指针得到

树的递归

此类题目用的是dfs或回溯在树中的应用

• 113-https://leetcode.com/problems/path-sum-ii/

BST性质

还有一类是针对BST中序的题目。有时候先遍历完根据排序性质判断反而更简单，在遍历过程中进行操作比较难想

• 98. Validate Binary Search Tree
• 99. Recover Binary Search Tree

参考

• https://www.zhihu.com/question/280279208