LeetCode 二叉树求最大深度

本文最后修改于 221 天前,部分内容可能已经过时!

原题目
____这是一道简单题,做法是比较多的。因为涉及到了整一棵树的最大深度,意味着一定要将整棵树全部遍历完成。那么和树的高度有关的遍历算法有哪些呢,答案是 层序遍历 和 深度优先遍历。一下使用这两种方式完成本题。

递归心得:不要去想整个递归对全局的所有影响,只要关注局部的处理结构能够拓展到全局就可以了,不然太麻烦了。

层序遍历代码:

    /**
 * 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) {
       int current1 = 1; //当前层的数量
       int current2 = 0; //下一层的数量
       int result = 0; //层数
       if(root == NULL) return 0;
        queue<TreeNode*> q;
        q.push(root);
        TreeNode* front;
        while(!q.empty()){
            front = q.front();
            if(front->left !=NULL){
                q.push(front->left);
                current2++;
            }
            if(front->right !=NULL){
                q.push(front->right);
                current2++;
            }
            q.pop();
            current1--;
            if(current1==0){
                result++;
                current1 = current2;
                current2 =0;
            }
        }
        return result;
    }
};

DFS:
递归完整代码:

    class Solution {
public:
    int dfs(TreeNode* root, int max_dept) {
        if(!root) return max_dept;
        int left_dept = dfs(root->left, max_dept+1);
        int right_dept = dfs(root->right, max_dept+1);
        return max(left_dept, right_dept);
    } 

    int maxDepth(TreeNode* root) {
        int max_dept = 0;
        return  dfs(root, max_dept);
    }
};

有一个精简版的DFS:

    class Solution {
public:
    int maxDepth(TreeNode* root) {
        return (root==NULL)? 0:max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

作者链接

Tags:DFS层序遍历
上一篇
打赏
下一篇

该页面评论已关闭