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

柔光的暖阳◎ 2022-06-11 02:24 228阅读 0赞

## 题目汇总 ##

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

目前范围：Leetcode前150题

### 生成二叉树 ###

*  [Construct Binary Tree from Preorder and Inorder Traversal (Inorder and Postorder)][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 Inorder Traversal 1]  
    后序遍历一个二叉树  
    **递归、迭代**

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

*  [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指向其左右节点的位置

[Construct Binary Tree from Preorder and Inorder Traversal _Inorder and Postorder]: http://blog.csdn.net/qqxx6661/article/details/75905524
[Convert Sorted Array to Binary Search Tree]: http://blog.csdn.net/qqxx6661/article/details/76100836
[Convert Sorted List to Binary Search Tree]: http://blog.csdn.net/qqxx6661/article/details/76168244
[Unique Binary Search Trees]: http://blog.csdn.net/qqxx6661/article/details/76285972
[Unique Binary Search Trees II]: http://blog.csdn.net/qqxx6661/article/details/76360113
[Binary Tree Preorder Traversal]: http://blog.csdn.net/qqxx6661/article/details/76602162
[Binary Tree Inorder Traversal]: http://blog.csdn.net/qqxx6661/article/details/76223471
[Binary Tree Inorder Traversal 1]: http://blog.csdn.net/qqxx6661/article/details/76602169
[Binary Tree Level Order Traversal]: http://blog.csdn.net/qqxx6661/article/details/75453452
[Binary Tree Level Order Traversal II]: http://blog.csdn.net/qqxx6661/article/details/76040001
[Binary Tree Zigzag Level Order Traversal]: http://blog.csdn.net/qqxx6661/article/details/75581367
[Path Sum]: http://blog.csdn.net/qqxx6661/article/details/76652929
[Path Sum II]: http://blog.csdn.net/qqxx6661/article/details/76696861
[Maximum Depth of Binary Tree]: http://blog.csdn.net/qqxx6661/article/details/75676272
[Minimum Depth of Binary Tree]: http://blog.csdn.net/qqxx6661/article/details/76602144
[Validate Binary Search Tree]: http://blog.csdn.net/qqxx6661/article/details/76474534
[Recover Binary Search Tree]: http://blog.csdn.net/qqxx6661/article/details/76565882
[Same Tree]: http://blog.csdn.net/qqxx6661/article/details/76565957
[Symmetric Tree]: http://blog.csdn.net/qqxx6661/article/details/75332482
[Balanced Binary Tree]: http://blog.csdn.net/qqxx6661/article/details/76602100
[Flatten Binary Tree to Linked List]: http://blog.csdn.net/qqxx6661/article/details/76652924
[Sum Root to Leaf Numbers]: https://blog.csdn.net/qqxx6661/article/details/78536789
[Binary Tree Maximum Path Sum]: https://blog.csdn.net/qqxx6661/article/details/78484940
[Populating Next Right Pointers in Each Node I and II]: https://blog.csdn.net/qqxx6661/article/details/78456278