图（dfs与bfs）算法2

进度：15/100

原题1：

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

（力扣的图）

原题2：

给定二叉树的根节点 root ，返回所有左叶子之和。

原题3：

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

原题4：

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

有效 二叉搜索树定义如下：

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

1.翻转二叉树--简单

这次一反常态没写出递归写出了迭代。

（1.迭代。每层每层反转，x.right<-->x.left，若左右节点是存在的，就加入队列。

（2.递归。有点抽象，自下而上翻转二叉树，因为叶节点反转好就可以反转子节点，而迭代是自上而下翻转二叉树。

2.左叶子之和--简单

思路：

（1.递归。由于要计算的是“左”叶子之和，所以递归return的标志不应该是发现该节点为叶子节点然后贡献给结果，而是发现当前节点的左子节点为叶子节点然后贡献给结果。

（2.迭代。对于每个节点，若该节点的左节点是叶子节点，贡献值；若不是叶子，加入栈中。对于右节点，若不是叶子节点，加入栈中。

3.二叉树的所有路径--简单

思路：

（1.递归。感谢 to_string 救我于水火之中。

（2.迭代。感觉迭代的逻辑总是很强。用一个treenode队列和一个string队列来存当前到达节点和路径，若该节点已经是叶子，就将路径push进vector中，若不是，则分别判断是否存在左子节点和右子节点，然后push进两个队列中。

学到写法：q.push(path + "->" + to_string( root->left->val ));

4.验证二叉搜索树--中等

（1.递归。感觉官方题解的代码好优美啊。从上往下递归的时候，函数带有root,lower,upper，如果root的val不满足大于lower或者小于upper，就return false，否则，继续向下遍历，遍历左节点就将upper更新为root.val（因为对于左节点来说，root.val是比它大的最小数），右节点就更新lower为root.val（对于右节点来说，root.val是比它小的最大数）。

（2.迭代。我们用中序遍历，那么该树如果是二叉搜索树，就一定是升序的。每次记录最小值，然后将下一个值与最小值比较，如果小于最小值，就说明不是二叉搜索树。我还是有点迷惑，可能本质上是因为我并没有完全搞懂遍历算法。