知识点

1. 知识点

   1. 二叉树的路径问题，一般都是通过DFS即可解决。

LeetCode算法

1. LeetCode算法

   1. 543.【二叉树的直径】

      解题思路：

      二叉树的直径为二叉树路径-1。

      首先，任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。

      因此，过二叉树的某个节点的最大路径=过左子树的最大节点数+过右子树的最大节点数+2。因此，我们可以遍历整个二叉树得到全部节点的最大路径，选最大的-1即可得到结果。即二叉树的最大直径=过左子树的最大节点数+过右子树的最大节点数+1

      子树的最大节点数=子树的最大深度。

   2. 113.【路径总和II】

      解题思路：

      利用回溯算法，找到符合的路径即可。

   3. 99.【恢复二叉搜索树】

      解题思路：

      思路1：

      首先，因为这是个二叉搜索树的题目，先考虑是否和二叉搜索树的特性有关。

      根据二叉搜索树的遍历特性可知，中序遍历的二叉搜索树一定为一个递增列表。

      因此，如果在一个递增的序列中交换两个值，有两种交换的情况。1、不相邻的两个数交换了，交换后的数组中假设前面的数为a[i]，后面的为a[j]，一定有a[i]>a[i+1]，a[j]<a[j-1]，因此只要遍历数组同时找到这两种情况即可找到两个错误交换的数a[i]和a[j+1]；2、相邻的两个数交换了，则前面数为a[i]，后面的为a[i+1]，一定有且只有a[i]>a[i+1]，如果出现并且只出现这种情况，则两个数找到了a[i]和a[i+1]。

      至此，我们使用一个数组存储二叉排序树的中序遍历情况，然后遍历中序排序数组找到两个节点，然后遍历二叉树重新给两个节点赋正确的值即可实现。

      时间复杂度：O(N)，其中 N 为二叉搜索树的节点数。中序遍历需要 O(N) 的时间，判断两个交换节点在最好的情况下是 O(1)，在最坏的情况下是 O(N)，因此总时间复杂度为 O(N)

      空间复杂度：O(N)，因为要开辟一个中序遍历的数组，数组大小与二叉搜索树的节点数相关。

      思路2：

      Mirrors算法，强化训练使用。

      时间复杂度：O(N)

      空间复杂度：O(1)