ARTS #016

ARTS is an activity initiated by 由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.

ARTS 016

This is article 16

Algorihm algorithm question

I did two questions this week, both related to binary tree calculations, and were implemented using recursion and iteration respectively.

226. Invert Binary Tree flip 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

Question Difficulty: Easy

Given a binary tree and a target sum, determine whether there is a path from the root node to the leaf node in the tree. The sum of all node values on this path is equal to the target sum.

Description: Leaf nodes refer to nodes that have no child nodes.

Example: Given the following binary tree, as well as the target and sum = 22,

              **5**
             / \
            **4 **  8
           /   / \
          **11 ** 13  4
         /  \      \
        7    **2**      1

Returns true because there is a path 5->4->11->2 from the root node to the leaf node with target sum 22.

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 as an article alone:

https://dandan2009.github.io/2018/11/22/data-structures-diving-into-data-structures-part1/

TIPS

• Different meanings of NULL, nil, Nil NSNull

  flag	value	meaning
  NULL	(void *)0	The literal zero value of a C pointer
  nil	(id)0	The literal zero value of an Objective-C object
  Nil	(Class)0	The literal zero value of an Objective-C class
  NSNull	[NSNull null]	A single object used to represent a zero value

  Reference: https://nshipster.cn/nil/

• In order to facilitate translation, I used Youdao SDK to make a translation tool. The input is a text file, and the output is also a text file, which is translated segment by segment. See also:

  https://github.com/dandan2009/youdaoTranslate

Share

As an iOS developer, how to learn Java in order to read the fourth edition of the algorithm? How to set up a java development environment?