Skip to content

Latest commit

 

History

History
50 lines (49 loc) · 1.62 KB

104. Maximum Depth of Binary Tree.md

File metadata and controls

50 lines (49 loc) · 1.62 KB

思路

思路一: 递归

最简单的思路就是递归。若树非空,则树高就是: 1 + max(左子树高,右子树高),递归出口就是树为空。

思路二: 非递归

可考虑用层序遍历的方法计算树高。
用last指针表示每一层的最后一个节点,每当遍历到这个节点即将树高加1并更新last指针。
last初始为root,后面每当遍历完每层最后一个节点后,即将last更新成下一层的最后一个节点,为此需要用一个tmp来不断记录能确定的下一层的最右节点。

C++

思路一

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

思路二

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int res = 0;
        queue<TreeNode *>q;
        TreeNode *p, *tmp=NULL, *last=root;  // tmp用来更新last用
        q.push(root);
        while(!q.empty()){
            p = q.front();
            q.pop();
            if(p -> left){
                tmp = p -> left;
                q.push(tmp);
            }
            if(p -> right){
                tmp = p -> right;
                q.push(tmp);
            } // tmp记录了直到现在下一层最右的节点 
            if(p == last){ // 遇到了last
                res++; // 树高加1
                last = tmp; // 更新last
            }
        }
        return res;
    }
};