参考：

基础算法(二) — BFS

待完成

96. 不同的二叉搜索树

已完成题目

图片.png 递归函数什么时候要有返回值，什么时候没有返回值

图片.png

二叉树的遍历方式

图片.png

538. 把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：
二叉树 - 图5
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1] 输出：[1,null,1]
示例 3：
输入：root = [1,0,2] 输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1] 输出：[7,9,4,10]

提示：

  • 树中的节点数介于 0 和 104 之间。
  • 每个节点的值介于 -104 和 104 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。

通过次数107,248
提交次数153,569

中序遍历的逆方向看，同时用temp保存当前值

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def convertBST(self, root: TreeNode) -> TreeNode:
  9.         temp = 0
  10.         o = root
  11.         def post_travese(root):
  12.             nonlocal temp
  13.             if not root:
  14.                 return
  15.             post_travese(root.right)
  16.             temp += root.val
  17.             root.val = temp 
  18.             post_travese(root.left)
  19.         post_travese(o)
  20.         return root
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     int sum = 0;
  18.     public TreeNode convertBST(TreeNode root) {
  19.         TreeNode o = root;
  20.         dfs(o);
  21.         return root;
  22.     }
  24.     public void dfs(TreeNode root){
  25.         if (root == null) {
  26.             return;
  27.         }
  28.         dfs(root.right);
  29.         sum += root.val;
  30.         root.val = sum;
  31.         dfs(root.left);
  32.     }
  33. }

图片.png

127. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

  • 序列中第一个单词是 beginWord 。
  • 序列中最后一个单词是 endWord 。
  • 每次转换只能改变一个字母。

  • 转换过程中的中间单词必须是字典 wordList 中的单词。


    给你两个单词beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
    示例 1：
    输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] 输出：5 解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。
    示例 2：
    输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”] 输出：0 解释：endWord “cog” 不在字典中，所以无法进行转换。

提示：

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord、endWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同

通过次数122,730
提交次数262,390

94. 二叉树的中序遍历

二叉树 - 图7
给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
二叉树 - 图8二叉树 - 图9
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[2,1]
示例 5：
输入：root = [1,null,2] 输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  9.         res = []
  10.         self.dfs(root, res)
  11.         return res 
  13.     def dfs(self, root, res):
  14.         if not root:
  15.             return 
  16.         self.dfs(root.left, res)
  17.         res.append(root.val)
  18.         self.dfs(root.right, res)

栈

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  9.         stack = []
  10.         res = []
  11.         while stack or root:
  12.             while root:
  13.                 stack.append(root)
  14.                 root = root.left
  15.             node = stack.pop()
  16.             res.append(node.val)
  17.             root = node.right
  18.         return res

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

二叉树 - 图10二叉树 - 图11

示例 1：
输入：root = [2,1,3] 输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

通过次数345,784
提交次数988,867

错误答案

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def isValidBST(self, root: TreeNode) -> bool:
  9.         flag = True
  10.         def dfs(root):
  11.             if not root:
  12.                 return 
  13.             left = dfs(root.left)
  14.             right = dfs(root.right)
  15.             if left.val >= root.val or right.val <= root.val:
  16.                 flag = False
  17.                 return 
  18.         return flag

以为没考虑到这种情况
二叉树 - 图12

递归

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def isValidBST(self, root: TreeNode) -> bool:
  9.         pre = None
  10.         def dfs(root):
  11.             nonlocal pre 
  12.             if not root:
  13.                 return True 
  14.             is_left_valid = dfs(root.left)
  15.             if pre is None:
  16.                 pre = root.val
  17.             elif pre < root.val:
  18.                 pre =  root.val
  19.             else:
  20.                 return False 
  21.             is_right_valid = dfs(root.right)
  22.             return is_left_valid and is_right_valid
  23.         return dfs(root)

迭代，中序遍历后判断是否有序

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def isValidBST(self, root: TreeNode) -> bool:
  9.         if not root:
  10.             return True
  11.         res =[]
  12.         def in_order(root):
  13.             if not root:
  14.                 return 
  15.             in_order(root.left)
  16.             res.append(root.val)
  17.             in_order(root.right)
  18.         in_order(root)
  19.         for i in range(1, len(res)):
  20.             if res[i-1] >= res[i]:
  21.                 return False
  22.         return True

112. 路径总和

二叉树 - 图13
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true
二叉树 - 图14
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false
示例 3：
输入：root = [1,2], targetSum = 0 输出：false

提示：

  • 树中节点的数目在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

通过次数266,554
提交次数506,807

参考
递归函数什么时候要有返回值，什么时候没有返回值，

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
  9.         def dfs(root, count):
  10.             if not root.left and not root.right and count == 0:
  11.                 return True  # 如果没有左右子树（到达叶子节点）且target也被消耗完了，则直接返回True,退出递归
  12.             if root.left: # 如果有左子树，则进入回溯
  13.                 count -= root.left.val
  14.                 if (dfs(root.left, count)): # 
  15.                     return True 
  16.                 count += root.left.val 
  17.             if root.right:
  18.                 count -= root.right.val
  19.                 if (dfs(root.right, count)):
  20.                     return True 
  21.                 count += root.right.val 
  22.             return False
  23.         if not root : 
  24.             return False
  25.         if not root.left and not root.right:
  26.             return targetSum == root.val
  27.         return dfs(root, targetSum - root.val)

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
二叉树 - 图15

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
二叉树 - 图16
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
示例 3：
输入：root = [1,2], targetSum = 0 输出：[]

提示：

  • 树中节点总数在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

通过次数177,610
提交次数283,414

带返回值的回溯

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def dfs(root, count, temp):
            if not root.left and not root.right and count == 0:
                res.append(temp[:])
            if not root.left and not root.right:
                return False 
            if root.left:
                temp.append(root.left.val)
                count -= root.left.val
                if (dfs(root.left, count, temp)):
                    return True 
                temp.pop(-1)
                count += root.left.val 
            if root.right:
                temp.append(root.right.val)
                count -= root.right.val
                if (dfs(root.right, count, temp)):
                    return True 
                temp.pop(-1)
                count += root.right.val 
            return False
        if not root:
            return []
        if not root.left and not root.right:
            if root.val == targetSum:
                return [[root.val]]
            else:
                return []
        dfs(root, targetSum - root.val, [root.val])
        return res

找一个路径，关键点是

if (dfs(root.left, count, temp)):
    return True

找到了，则直接返回，不再继续找了

不带返回值的回溯
图片.png
递归出所有的结果放在res里面

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def dfs(root, count, temp):
            if not root.left and not root.right and count == 0:
                res.append(temp[:])
            if not root.left and not root.right:
                return
            if root.left:
                temp.append(root.left.val)
                count -= root.left.val
                dfs(root.left, count, temp)
                temp.pop(-1)
                count += root.left.val 
            if root.right:
                temp.append(root.right.val)
                count -= root.right.val
                dfs(root.right, count, temp)
                temp.pop(-1)
                count += root.right.val 
        if not root:
            return []
        if not root.left and not root.right:
            if root.val == targetSum:
                return [[root.val]]
            else:
                return []
        dfs(root, targetSum - root.val, [root.val])
        return res

226. 翻转二叉树

图片.png

使用前序或者后序遍历来交换左右2个节点

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        def dfs(root):
            if not root:
                return 
            dfs(root.left)
            dfs(root.right)
            temp = root.left
            root.left = root.right
            root.right= temp
        dfs(root)
        return root

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        TreeNode o = root;
        postOrder(o);
        return root;
    }

    public TreeNode postOrder(TreeNode root){
        if (root == null) {
            return null;
        }
        TreeNode left = postOrder(root.left);
        TreeNode right = postOrder(root.right);
        TreeNode temp = left;
        root.left = right;
        root.right = temp;
        return root;
    }
}

对左右子树进行判断， 未AC，未完成

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return
        def post_order(left, right):
            if not left or not right:
                return
            temp = left.val 
            left.val = right.val
            right.val = temp
            # if left.left and right.right:
            post_order(left.left, right.right)
            # if left.right and right.left:
            post_order(left.right, right.left)
        o = root
        post_order(o.left, o.right)
        return root

需要考虑到没有子树的情况
图片.png

前序遍历解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root: return 
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / \ 2 2 / \ / \ 3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / \ 2 2 \ \ 3 3

进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
通过次数409,319
提交次数726,764

层序遍历解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        cur_queue = [root]
        while cur_queue:
            next_queue=[]
            li =[]
            for node in cur_queue:
                if not node:
                    li.append(None)
                    continue
                next_queue.append(node.left)
                next_queue.append(node.right)
                li.append(node.val)
            if li != li[::-1]:
                return False
            cur_queue = next_queue
        return True

递归解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True 
        def dfs(left, right):
            if not left and not right:
                return True 
            if left and not right:
                return False 
            if not left and right:
                return False
            if left.val != right.val:
                return False 
            outside = dfs(left.left, right.right)
            inside = dfs(left.right, right.left)
            return outside and inside
        return dfs(root.left, root.right)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return dfs(root.left, root.right);
    }

    public boolean dfs(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null | right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        boolean outside = dfs(left.left, right.right);
        boolean inside = dfs(left.right, right.left);
        return outside && inside;
    }
}

首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
图片.png
这题的逻辑是在2棵树上进行遍历

1. outside = dfs(left.left, right.right)
2. inside = dfs(left.right, right.left)

左子树是正常的 后续遍历 左右根
图片.png
右子树看成是后序遍历的改进， 右左根
图片.png

99. 恢复二叉搜索树

二叉树 - 图23
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：
输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2] 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
二叉树 - 图24
示例 2：
输入：root = [3,1,4,null,null,2] 输出：[2,1,4,null,null,3] 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

  • 树上节点的数目在范围 [2, 1000] 内
  • -231 <= Node.val <= 231 - 1

使用中序遍历转换为数组，再交换
但是判断数组哪2个点交换了，采用的是非常暴力的解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        res = []
        o = root
        def in_order(root):
            if not root:
                return 
            nonlocal res
            in_order(root.left)
            res.append(root.val)
            in_order(root.right)
        in_order(o)
        temp = sorted(res)
        print(res)
        print(temp)
        x, y = -1, -1
        for i in range(len(res)):
            if res[i] != temp[i]:
                if x == -1:
                    x = res[i]
                else:
                    y = res[i]
        print('x=',x)
        print ('y=',y)
        o2 = root
        def dfs(root):
            if not root: return
            if root.val == x:
                root.val = y
            elif root.val == y:
                root.val = x
            dfs(root.left)
            dfs(root.right)
        dfs(o2)

优化解法，利用引用，中序遍历，数组里放的是节点的引用，而不是val

class Solution(object):
    def recoverTree(self, root):
        nodes = []
        # 中序遍历二叉树，并将遍历的结果保存到list中        
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            nodes.append(root)
            dfs(root.right)
        dfs(root)
        x = None
        y = None
        pre = nodes[0]
        # 扫面遍历的结果，找出可能存在错误交换的节点x和y
        for i in xrange(1,len(nodes)):
            if pre.val>nodes[i].val:
                y=nodes[i]
                if not x:
                    x = pre
            pre = nodes[i]
        # 如果x和y不为空，则交换这两个节点值，恢复二叉搜索树 
        if x and y:
            x.val,y.val = y.val,x.val

作者：wang_ni_ma
链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/san-chong-jie-fa-xiang-xi-tu-jie-99-hui-fu-er-cha-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

别人的思路待完成
思路

中序遍历BST，依次访问的节点值是递增的，错误的BST会破坏递增性，从而能定位出错误。
我发现，错误有两种：

错误1：出现了两对不满足前小后大，需要交换第一对的第一个元素与第二对的第二个元素。<br />    错误2：只出现一对不满足前小后大，交换这一对元素即可。

图片.png

可以在的递归遍历过程中，将节点值推入一个数组，再遍历数组找出错误对。
但其实没必要。
只用比较前后访问的节点值，prev 保存上一个访问的节点，当前访问的是 root 节点。

每访问一个节点，如果prev.val>=root.val，就找到了一对“错误对”。
检查一下它是第一对错误对，还是第二对错误对。

遍历结束，就确定了待交换的两个错误点，进行交换。
代码

时间复杂度O(n)，n是节点个数，空间复杂度O(H)，递归栈的深度。

作者：xiao_ben_zhu
链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/tu-jie-hui-fu-yi-ge-er-cha-sou-suo-shu-by-hyj8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

108. 将有序数组转换为二叉搜索树

二叉树 - 图26
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
二叉树 - 图27
示例 2：
输入：nums = [1,3] 输出：[3,1] 解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。