The depth of a binary tree

Title: Daily practice (27) : The depth of binary trees

Categories: [sword refers to offer]

Tags: Daily Practice

date: 2022/02/26

Enter the root node of a binary tree to find the depth of the tree. The nodes (including root and leaf nodes) that pass from the root node to the leaf node form a path of the tree. The longest length of the path is the depth of the tree.

Such as:

Given a binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns its maximum depth of 3.

Tip:

The number of nodes is less than = 10000

Source: LeetCode

Link: leetcode-cn.com/problems/er…

Method one: recursion

Subsequent traversal:

Follow the recursive trilogy to see how to write it.

1. Determine the argument and return value of the recursive function: the argument is the root node of the passed tree, return the depth of the tree, so the return value is int. The code is as follows:

int getDepth(TreeNode* node)
Copy the code

2. Determine the termination condition: if the node is empty, return 0, indicating that the height is 0. The code is as follows:

if (node == NULL) return 0;
Copy the code

3. Determine the logic of single-layer recursion: first find the depth of its left subtree, then find the depth of its right subtree, and finally take the maximum value of left and right depth and then +1 (add 1 because the current middle node is included) is the depth of the tree whose current node is the root node.

int leftDepth = getDepth(node->left);       / / left
int rightDepth = getDepth(node->right);     / / right
int depth = 1 + max(leftDepth, rightDepth); / /
return depth;
Copy the code

Simplified before / / 1
int getDepth(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = getDepth(node->left);       / / left
    int rightDepth = getDepth(node->right);     / / right
    int depth = 1 + max(leftDepth, rightDepth); / /
    return depth;
}
int maxDepth(TreeNode* root) {
    return getDepth(root);
}
/ / 2 simplified
int maxDepth(TreeNode* root) {
    return (root == NULL)?0 : 1 + max(maxDepth(root->left), maxDepth(root->right));
}
Copy the code

Method 2: Iterative Method (BFS)

Using the iterative method, the sequential traversal is the most appropriate, because the maximum depth is the number of levels of the binary tree, which is very consistent with the sequential traversal

int maxDepth(TreeNode* root) {
	if (root == NULL) {
        return 0;
    }
    int depth = 0;
    queue<TreeNode*> que;
    que.push(root);
    while(! que.empty()) {
        depth++;
        int size = que.size(a);for (int i = 0; i < size; i++) {
            TreeNode* node = que.front(a); que.pop(a);if (node->left) {
                que.push(node->left);
            }
            if (node->right) {
                que.push(node->right); }}}return depth;
}
Copy the code

The depth of a binary tree