Day19 104二叉树的最大深度 559N叉树的最大深度 111二叉树的最小深度

104二叉树的最大深度

? ? ? ? 首先我们要理解二叉树的深度和高度都是什么？所谓深度，就是指当前结点距离根节点的距离，所谓高度，就是指当前结点距离叶子结点的距离，那么高度与深度又有什么关系呢？根节点的高度就等于二叉树的最大深度。

后序遍历

1.确定递归函数参数返回值：返回深度，传入根节点

2.确定终止条件：如果是空节点就返回0

3：单层递归逻辑：先求左子树深度，再求右子树深度，最后取左右深度最大数值加1就是中间节点的深度? 总体代码如下：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        return (leftDepth>rightDepth?leftDepth:rightDepth)+1;
    }
};

前序遍历

1.确定递归函数的参数和返回值：输入一个结点，以及此时的深度（这样才能累加）

2.终止条件：当结点为空的时候，就说明遍历到头了，返回此时的result

3.单层逻辑：前序遍历采取中左右的顺序，从上往下推，首先中节点判断之前返回的长度和存储的result哪个大，让result等于大的那个，左右分别继续递归，同时参数depth+1，因为是以左右为起点开始的，最后返回结果。

class Solution {
public:
    int result;
    int getDepth(TreeNode*node, int depth)
    {
        //终止条件
        if(node==nullptr) return result;
        //每层递归逻辑
        //中
        result = result > depth ? result : depth;
        //左
        int leftDepth = getDepth(node->left, depth+1);
        //右
        int rightDepth = getDepth(node->right, depth+1);
        return result;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if(root==nullptr) return result;
        return getDepth(root, 1);
    }
};

?层序遍历

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int depth = 0;
        if(root != nullptr)
            que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            depth++;
            while(size--)
            {
                TreeNode*node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return depth;
    }
};

559 N叉树的最大深度

与上面二叉树的类似，只是判断左右孩子的时候要利用for循环找到那个最大值了。这里提供后序和层序版本。

class Solution {
public:
    int maxDepth(Node* root) {
        if(root == nullptr) return 0;
        int depth = 0;
        for(int i = 0; i < root->children.size(); i++)
            depth = max(depth, maxDepth(root->children[i]));
        return depth + 1;
    }
};

class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> que;
        if(root!=nullptr) que.push(root);
        int depth = 0;
        while(!que.empty())
        {
            int size = que.size();
            depth++;
            while(size--)
            {
                Node*node = que.front();
                que.pop();
                for(int i = 0; i < node->children.size(); i++)
                    if(node->children[i]) que.push(node->children[i]);
            }
        }
        return depth;
    }

111 二叉树最小深度

后序遍历

? ? ? ? 与上一题基本类似，但是要注意一点，只有当左右孩子都没有时才能被认定为叶子结点，所以要进行一次特殊的判断：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);
        if(root->left == nullptr&& root->right!=nullptr)
            return 1 + rightDepth;
        if(root->left != nullptr&& root->right==nullptr)
            return 1 + leftDepth;
        return 1 + min(rightDepth,leftDepth);
    }
};

前序遍历

????????也与上一题要类似，但是要注意以下几点，首先就是中的处理逻辑中，要先判断是否是叶子节点，才能进行result的变值操作。第二点就是result初始值设为了0，这样不是很好，因为要判断最小值，最后都会变成0，于是result的初值设为INT-MAX，同时递归终止条件也返回INT_MAX。

public:
    int result;
    int getDepth(TreeNode*node, int depth)
    {
        //终止条件
        if(node==nullptr) return result;
        //每层递归逻辑
        //中
        if (node -> left == nullptr && node->right == nullptr)
        result = result < depth ? result : depth;
        //左
        int leftDepth = getDepth(node->left, depth+1);
        //右
        int rightDepth = getDepth(node->right, depth+1);
        return result;
    }
    int minDepth(TreeNode* root) {
        result = INT_MAX;
        if(root==nullptr) return 0;
        return getDepth(root, 1);
    }
};

层序遍历

这里的左右孩子如果都为空，说明就到最低点了，后面就不用遍历了！

class Solution {
public:

    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;
    }
};

? ? ? ? ?今天主要是写了二叉树的最大和最小深度，首先要明白高度和深度的区别，一般前序遍历算深度，后序遍历算高度。同时要注意最小深度的那个陷阱，只有左右节点都为空才能被视为叶子节点。