算法训练营day16(11.14)

题目1： 513. 找树左下角的值

算法思路：
使用层序遍历得到包含数的所有结点的vector<vector<int>>。然后提取最后一个vector中的最后一个元素即可。

题目2： 112. 路径总和

算法思路：
需要用深度优先搜索，从根节点开始遍历，并记录下从根结点到当前结点的路径以及路径和。所以可以设计一个辅助函数，类似下面声明：
bool hasPathSum(TreeNode* root, vector<int>& path, int curSum, int targetSum)
然后从根结点开始遍历。
1）如果根结点为空，直接返回false
2）将当前结点加入path中，然后判断当前结点是否为叶子结点，若为真，则判断当前路径和是否等于目标和，相等则直接返回true。
3）判断当前结点左孩子是否为空，若不空，则对其递归调用这个函数，其结果为真则返回true。否则需要弹出path的最后一个元素(即左孩子)
4）判断当前结点右孩子是否为空，若不空，则对其递归调用这个函数，其结果为真则返回true。否则需要弹出path的最后一个元素(即右孩子)

题目3： 113. 路径总和 II

算法思路：
跟112类似，只是辅助函数中需要添加一个vector<vector<int>>& vec用于存储所有满足要求的结果。
算法中每次找到匹配结果时直接将path加入到vec中，但并不返回并继续向下执行。

题目4：106. 从中序与后序遍历序列构造二叉树

算法思路：
这个算法相对来说比较简单，需要设计一个辅助函数，其声明如下：
// inorder[leftIo, rightIo), postorder[leftPo, rightPo)
TreeNode* buildTree(vector<int>& inorder, int leftIo, int rightIo, vector<int>& postorder, int leftPo, int rightPo)
然后需要很容易根据后序遍历的特点知道其最后一个元素即为根结点的值。
再从inorder数组中找到根结点对应的索引值并将inorder由此划分成左右子树，postorder数组也可以得到对应的左右子树对应的postorder索引号，然后构造左右子树即可。