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

原博客地址：https://blog.****.net/qqxx6661/article/details/76223475

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

一.生成二叉树（递归、卡特兰数)。

1.106 Construct Binary Tree from Inorder and Postorder Traversal

根据前序和中序(后序和中序）构造二叉树。

2.107 中序和后序生成二叉树

3.Convert Sorted Array to Binary Search Tree

数组转化为二叉树

4.Convert Sorted List to Binary Search Tree

链表转化为平衡二叉树。

思路：先把链表转化为list数组，然后像上个题一样转化为二叉树。

下图代码，红框是把链表转化为数组

5.Unique Binary Search Trees II

.

上面那个题，

Unique Binary Search Trees 不理解状态转移矩阵，需要复习一下卡特兰数相关的知识。

二.二叉树的遍历(迭代）

1.前序遍历(leetcode 144题）

解：

如何船root进去

2.145后序遍历

后序遍历是 左右根，为了方便，遍历 根右左，然后倒叙输出

3.中序遍历(leetcode 94)

4.层次遍历（leetcode102）

5.其他两个层次遍历和上面的非常相似，没记录

6.path sum(leetcode 112)

博客链接：

https://segmentfault.com/a/1190000003554851

7.path sum 2(leetcode 113)

三.二叉树的遍历（递归）

1.后序遍历

2.中序遍历

3.前序遍历

四.其他

1.求树的最大深度

思路：分别遍历根节点的左右子树(p.s.根节点是相对而言的，不只是最初的根节点)，遍历一层，加一，取能遍历的最大值。

2、求树的最小深度

为什么最小深度要考虑左右子树，因为左子树为空时，选的是min值，return的会一直是0，因此要考虑。而最大深度，是max，空不空对它没影响。

3.判断是否对称（leetcode 101）

思路：

4.判断是否为二叉树（leetcode 98）

5.Recover Binary Search Tree(leetcode 99)

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

用pre存中序遍历时当前节点的前一个节点，方便值的大小对比，用n1，n2记录这两个不合法序列的位置，n1存较大的值，n2存较小的值。

6. same tree(leetcode 100)

7.Balanced Binary Tree（leetcode 110）

8.Flatten Binary Tree to Linked List(leetcode 114)

上面是题目及提示信息，大概意思是要按照前序遍历的顺序，将其变成一个但链表（但还是用树结构存

(https://www.cnblogs.com/nashiyue/p/5313767.html)

解答来源于博客

https://blog.****.net/lu_gee/article/details/77461156