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。

;