Leetcode Study Day 32

Maximum Depth of Binary 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.

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:

Input: root = [1,null,2]
Output: 2
 

Constraints:

The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100

My solution

My solution is to create a recursive function, in this function, we pass two parameters, one is the node, the other is the current depth so far. If the node is null, we return the current depth. If the node is not null, we call the function recursively on the left and right child of the node, and return the maximum of the two depths.

int passDepth(TreeNode* node, int depth){
    if (!node) return depth;
    else{
        depth ++;
        return max(passDepth(node->left, depth),passDepth(node->right,depth));
    }
}

Full code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int passDepth(TreeNode* node, int depth){
        if (!node) return depth;
        else{
            depth ++;
            return max(passDepth(node->left, depth),passDepth(node->right,depth));
        }
    }

    int maxDepth(TreeNode* root) {
        int depth = 0;
        return passDepth(root,depth);
    }
};

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:


Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:


Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:


Input: p = [1,2,1], q = [1,1,2]
Output: false

My solution

For this question, we create a recursive function to solve this question. The main idea is if the current node 1 and node 2 is null, we return true, else we return false. If the current node 1 and node 2 have the same value, we pass their left and right nodes into this function again. If the current node 1 and node 2 have different values, we return false.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q)
            return true;
        else if (!p || !q)
            return false;
        if(p->val != q->val)
            return false;
        else{
            return(isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
        }
    }
};