145. Binary Tree Postorder Traversal

tags: Easy、Tree

Given the root of a binary tree, return the postorder traversal of its nodes' values.

解法1: 效能較差(多用一個變數) but 易讀性高

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void postTrace(struct TreeNode* t, int* array, int* index) {
    if (!t) {
        return;
    }
    postTrace(t->left, array, index);
    postTrace(t->right, array, index);
    array[*index] = t->val;
    (*index)++;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    int index = 0;
    int* array = (int*)malloc(100 * sizeof(int));

    postTrace(root, array, &index);
    *returnSize = index;
    return array;
    
}

解法2: 效能較好

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void postTrace(struct TreeNode* t, int* array, int* index) {
    if (!t) {
        return;
    }
    postTrace(t->left, array, index);
    postTrace(t->right, array, index);
    array[*index] = t->val;
    ++(*index);
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* array = (int*)malloc(100 * sizeof(int));
    postTrace(root, array, returnSize);
    return array;
    
}

2331. Evaluate Boolean Binary Tree

tags: Easy、Tree

You are given the root of a full binary tree with the following properties:
Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.
The evaluation of a node is as follows:
If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.
Return the boolean result of evaluating the root node.
A full binary tree is a binary tree where each node has either 0 or 2 children.
A leaf node is a node that has zero children.

解法1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int value(struct TreeNode* node) {
    if (node->left != NULL && node->right != NULL) {
        if (node->val == 2) {
            return value(node->left) | value(node->right);
        }
        else {
            return value(node->left) & value(node->right);
        }
    }
    else {
        return node->val;
    }
}


bool evaluateTree(struct TreeNode* root) {
    if (!root) {
        return NULL;
    }
    return value(root);
    
}

解法2:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int value(struct TreeNode* node) {
    if (!node){
        return NULL;
    }
    value(node->left);
    value(node->right);
    if (node->left != NULL && node->right != NULL) {
        if (node->val == 2) {
            node->val = (node->left->val) | (node->right->val);
            // return value(node->left) | value(node->right);
        }
        else {
            node->val = (node->left->val) & (node->right->val);
            // return value(node->left) | value(node->right);
        }
    }
    return node->val;

}


bool evaluateTree(struct TreeNode* root) {
    // if (!root) {
    //     return NULL;
    // }
    value(root);
    return root->val;
    
}

993. Cousins in Binary Tree

tags: Easy、Tree

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.
Two nodes of a binary tree are cousins if they have the same depth with different parents.
Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

解法1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int nodeHeight(struct TreeNode* node, int value, int height) {
    if (!node) {
        return -1;
    }

    if (node->val == value) {
        return height;
    }

    int leftHeight = nodeHeight(node->left, value, height + 1);
    if (leftHeight != -1) {
        return leftHeight;
    }
    return nodeHeight(node->right, value, height + 1);
}

bool hasSameParent(struct TreeNode* node, int x, int y) {
    if (!node) {
        return false;
    }
    if (node->left && node->right) {
        if ((node->left->val == x && node->right->val == y) || 
            (node->left->val == y && node->right->val == x)) {
            return true;
        }
    }
    return hasSameParent(node->left, x, y) || hasSameParent(node->right, x, y);
}

bool isCousins(struct TreeNode* root, int x, int y) {
    if (!root) {
        return false;
    }
    if (root->left && root->right) {
        if ((root->left->val == x && root->right->val == y) || 
            (root->left->val == y && root->right->val == x)) {
            return false;
        }
    }
    int heightX = nodeHeight(root, x, 0);
    int heightY = nodeHeight(root, y, 0);
    return (heightX == heightY) && !hasSameParent(root, x, y);
}

解法2:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 找到此val的node
struct TreeNode* findNode(struct TreeNode* node, int value) {
    if (!node) {
        return NULL;
    }
    if (node->val == value) {
        return node;
    }

    struct TreeNode* result = findNode(node->left, value);
    return (result != NULL) ? result : findNode(node->right, value); 
}

//找到該node的高度
int nodeHeight(struct TreeNode* root, struct TreeNode* node, int height) {
    if (!root) {
        return -1;
    }

    if (root == node) {
        return height;
    }

    int left_height = nodeHeight(root->left, node, height+1);
    return (left_height != -1) ? left_height : nodeHeight(root->right, node, height+1);
}

//是否有相同的parent
bool hasSameParent(struct TreeNode* root, struct TreeNode* x_node, struct TreeNode* y_node) {
    if (!root) {return false;}

    return ((root->left == x_node && root->right == y_node) || 
            (root->left == y_node && root->right == x_node) ||
            hasSameParent(root->right, x_node, y_node) ||
            hasSameParent(root->left, x_node, y_node));
}

bool isCousins(struct TreeNode* root, int x, int y) {
    struct TreeNode* x_node = findNode(root, x);
    struct TreeNode* y_node = findNode(root, y);
    int x_height = nodeHeight(root, x_node, 0);
    int y_height = nodeHeight(root, y_node, 0);

    return ((x_height == y_height) && (!hasSameParent(root, x_node, y_node)));
}

104. Maximum Depth of Binary Tree

tags: Easy、Tree

Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

解法1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int getHeight(struct TreeNode* node, int height) {
    if (node == NULL) {
        return height;
    }
    int left_height = getHeight(node->left, height+1);
    int right_height = getHeight(node->right, height+1);

    return (left_height > right_height) ? left_height : right_height;
}
int maxDepth(struct TreeNode* root) {
    return getHeight(root, 0);
}

解法2:

int maxDepth(struct TreeNode* root) {
    if (!root) {
        return 0;
    }

    int left_depth = maxDepth(root->left);
    int right_depth = maxDepth(root->right);
    return ((left_depth >= right_depth) ? left_depth : right_depth) + 1;
}