【LeetCode】二叉树的最大深度

【问题】给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

/ \

/ \

 7

返回它的最大深度 3 。

【DFS解法】

我们使用栈结构来储存每个节点root以及该节点的深度deep，由于对tuple的使用还不太熟练，需要多练习，一次使用tuple来讲树结构体指针和对应的整型变量深度。从根节点开始遍历，首先一直遍历左子节点，并将节点压入栈中，如果左子节点为空，则从栈中弹出，并开始遍历弹出节点的右子节点。这个过程也就相当于回溯了，回到上一级去。

**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    int maxDepth(TreeNode* root) {

        if (root == nullptr)  return ;

        stack<tuple<TreeNode*, int>> sta;

        int maxdeep = ;

        int deep = ;

        while(!sta.empty() || root){

            while(root){

                sta.push(make_tuple(root, deep+));

                deep++;

                root = root->left;

            }

            tie(root, deep) = sta.top();

            if(maxdeep < deep) maxdeep = deep;

            sta.pop();

            root = root->right;

        }

        return maxdeep;

    }

};

【BFS解法】

这个其实质就是层次遍历，使用队列来储存树节点，并使用size变量记录每次节点的数量，在一次循环中，处理掉一层的节点，具体做法：将某一层所有节点的子节点压入队列后，并将所有的节点移除队列。
在处理某一层的树节点的同时，使用count变量记录处理的层数。即为最大深度！

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    int maxDepth(TreeNode* root) {

        if(root == nullptr){

            return ;

        }

        queue<TreeNode*> que;

        que.push(root);

        int count = ;

        while(que.size() != ){

            int size = que.size();

            while(size--){

                TreeNode* tmp = que.front();

                if(tmp->left != nullptr) que.push(tmp->left);

                if(tmp->right != nullptr) que.push(tmp->right);

                que.pop();

            }

            count++;

        }

        return count;

    }

};

巴特西

【LeetCode】二叉树的最大深度

最新文章

热门文章