ARTS是
由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS），至少坚持一年。
ARTS 016
这是第16篇
Algorihm 算法题
本周做了两道题，都是算二叉树相关的，分别用递归和迭代实现。
226. Invert Binary Tree 翻转二叉树
Difficulty: Easy
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9```
Output:
4 / \ 7 2 / \ / \ 9 6 3 1```
Trivia:
This problem was inspired by by :
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
Solution
Language: C
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* invertTree(struct TreeNode* root) {
}
//递归 rcursive
struct TreeNode* invertTree_1(struct TreeNode* root) {
if (root == NULL) {
return root;
}
if(root->left != NULL || root->right != NULL){
struct TreeNode *temp = root->left;
root->left = root->right;
root->right = temp;
}
if(root->left)
invertTree(root->left);
if(root->right)
invertTree(root->right);
return root;
}
//迭代 iteratively
struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL) {
return root;
}
struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
int stackCount = 0;
struct TreeNode* p = root;
while (p) {
if (p->right) {
stack[stackCount++] = p->right;
}
if (p->left || p->right) {
struct TreeNode *temp = p->left;
p->left = p->right;
p->right = temp;
}
p = p->right;
if (!p && stackCount >0) {
p = stack[--stackCount];
}
}
return root;
}
112. 路径总和(Path Sum)
题目难度： 简单
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
**5**
/ \
**4 ** 8
/ / \
**11 ** 13 4
/ \ \
7 **2** 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
Solution
Language: C
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool hasPathSum(struct TreeNode* root, int sum) {
}
//递归 rcursive
bool hasPathSum_1(struct TreeNode* root, int sum) {
if (!root) {
return false;
}
if (root->left || root->right) {
return (hasPathSum(root->left,sum - root->val) || hasPathSum(root->right,sum - root->val));
}
return root->val == sum;
}
//迭代 iteratively
bool hasPathSum(struct TreeNode* root, int sum) {
if (root == NULL) {
return root;
}
struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
int * sumStack = (int *)malloc(sizeof(int *) * (1000));
int stackCount = 0;
stack[stackCount]=root;
sumStack[stackCount] = sum - root->val;
stackCount++;
while (stackCount >0) {
stackCount--;
struct TreeNode* p = stack[stackCount];
int leftsum = sumStack[stackCount];
printf("leftsum:%d",leftsum);
if (!p->left && !p->right && leftsum==0) {
return true;
}
if (p->left) {
stack[stackCount]=p->left;
sumStack[stackCount] = leftsum - p->left->val;
stackCount++;
}
if (p->right) {
stack[stackCount]=p->right;
sumStack[stackCount] = leftsum - p->right->val;
stackCount++;
}
}
return false;
}
Review
Review单独作为一篇文章：
https://dandan2009.github.io/2018/11/22/data-structures-diving-into-data-structures-part1/
TIPS
-
NULL、nil、Nil NSNull的不同含义
标志 值 含义 NULL (void *)0 C指针的字面零值 nil (id)0 Objective-C对象的字面零值 Nil (Class)0 Objective-C类的字面零值 NSNull [NSNull null] 用来表示零值的单独的对象 参考：https://nshipster.cn/nil/
-
为了方便翻译，我用有道SDK做了一个翻译的工具，输入是text文件，输出也text文件，按段翻译。 参见：
https://github.com/dandan2009/youdaoTranslate
Share
作为一名iOS开发者，为了看算法第四版，如何学习java？如何搭建java开发环境？
