513.找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
提示:
- 二叉树的节点个数的范围是
[1,104] -2^31 <= Node.val <= 2^31 - 1
思路：
这道题要求我们找到二叉树的最底层最左边节点，我们可以用层序遍历，遍历到最后出来的是一个拥有每一层遍历元素的一个二维数组，我们只需要取得二维数组的最后一位的第一个索引的元素我们就能得到最终的答案。
解答：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int** leveltravel(struct TreeNode* root,int* returnsize)
{if(root == NULL){*returnsize = 0;return NULL;}int** result = malloc(sizeof(int*)*10000);*returnsize = 0;struct TreeNode* queue[10000];int front = 0;int rear = 0;queue[rear++] = root;while(front < rear){int levelsize = rear - front;result[*returnsize] = malloc(sizeof(int)*levelsize);for(int i = 0;i < levelsize;i++){struct TreeNode* node = queue[front++];result[*returnsize][i] = node->val;if(node->left != NULL)queue[rear++] = node->left;if(node->right != NULL)queue[rear++] = node->right;}(*returnsize)++;}return result;
}
int findBottomLeftValue(struct TreeNode* root) {int returnsize = 0;int** result = leveltravel(root,&returnsize);return result[returnsize-1][0];
}
112.路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
思路：
这道题最开始想的迭代，但是没做出来，后面看来解析，看用的递归和回溯，递归看懂了，但是回溯有点似懂非懂，接下来我来讲解一下我的思路。首先，我们建立一个递归函数，找到递归结束的基线条件，那就是到叶节点时，相加的值等于目标值，也就是说我们每做实现一次递归，我们都要判断他是否满足基线条件，满足的话返回true，不满足的话继续找，直到找不到返回false。
解答：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
bool leveltravel(struct TreeNode* root,int count)
{if(root->left ==NULL && root->right == NULL && count == 0)return true;if(root->right == NULL && root->left == NULL)return false;if(root->left != NULL){count -= root->left->val;if(leveltravel(root->left,count) == true)return true;count += root->left->val;}if(root->right != NULL){count -= root->right->val;if(leveltravel(root->right,count) == true)return true;count += root->right->val;}return false;
}
bool hasPathSum(struct TreeNode* root, int targetSum) {if(root == NULL)return false;return leveltravel(root,targetSum-(root->val));
}
106.从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成postorder中每一个值都在inorder中inorder保证是树的中序遍历postorder保证是树的后序遍历
思路：
这道题有点不会，还需要多次去复习，等二刷的时候再做。
解答：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int findIndex(int* arr, int start, int end, int value) {for (int i = start; i <= end; i++) {if (arr[i] == value) {return i;}}return -1;
}
struct TreeNode* TreeHelp(int* inorder,int instart,int inend,int* postorder, int* postIndex)
{if (instart > inend) {return NULL;}int rootValue = postorder[*postIndex];(*postIndex)--;struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = rootValue;root->left = NULL;root->right = NULL;int inIndex = findIndex(inorder, instart, inend, rootValue);root->right = TreeHelp(inorder, inIndex + 1, inend, postorder, postIndex);root->left = TreeHelp(inorder, instart, inIndex - 1, postorder, postIndex);return root;
}
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {postorderSize = postorderSize - 1;return TreeHelp(inorder,0,inorderSize-1,postorder,&postorderSize);
}
反思
今天的难度适中，最后一道题不好做，另外两道还好，对于回溯算法和二叉树的一些基本操作有一定的了解了。
