leetcode 104. 二叉树的最大深度

题目描述：

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

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

思路：先想想递归该怎么做。如果一个节点是NULL，那么它的最大深度应该是0；如果它是一个孤立的节点，那么它的深度是1；否则它的深度应该是它所有孩子节点的最大深度+1。关系清晰明了，代码也很简单，如下：

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

注意到其实第二个if语句作为递归出口，并不是必要的：因为对于孤立节点来说，它的孩子节点都是NULL，两个子树深度都是0，可以+1得到它自身的深度。好玩心起改写成1行代码：

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

上面两个算法时间复杂度都是O(n)，测试运行时间都是 4ms。

下面试试能不能改成迭代算法：

最大深度，其实就是树的层数。所以模仿层序遍历就好了。不过这里要注意，要把层与层之间分开，然后统计遍历的层数。

int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        //不能用栈，用队列
        queue<TreeNode*> q;
        int ans=0;
        //用NULL作为层与层之间的分隔标志
        q.push(root);
        q.push(NULL);
        while(true)
        {
            //每多一层，ans+1
            ans++;
            root=q.front();
            q.pop();
            while(root)
            {
                //既然NULL作为分隔标志了，这里的NULL就不能进入队列了
                if(root->left) q.push(root->left);
                if(root->right) q.push(root->right);
                root=q.front();
                q.pop();
            }
            if(q.size()==0) return ans;
            q.push(NULL);
        }
    }

时间复杂度仍旧是O(n)，测试运行时间 8ms。

;

Popular Programs