代码随想录算法训练营

代码随想录算法训练营Day16二叉树|104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

104.二叉树的最大深度

题目链接：104.二叉树的最大深度

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

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

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

示例：给定二叉树 [3,9,20,null,null,15,7]，返回最大深度3

总体思路

递归法

使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）

而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

这一点其实是很多同学没有想清楚的，很多题解同样没有讲清楚。

我先用后序遍历（左右中）来计算树的高度。

代码实现：

int getdepth(treenode* node)

确定终止条件：如果为空节点的话，就返回0，表示高度为0。

if(node==NULL) return 0;

确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

int leftdepth=getdepth(node->left);    //左

int rightdepth=getdepth(node->right);  //右

int depth=1+max(leftdepth,rightdepth); //根

return depth;

整体代码：

class solution{

public:

	int getdepth(treenode* node){

		if(node==NULL) return 0;

		int leftdepth=getdepth(node->left);    //左

		int rightdepth=getdepth(node->right);  //右

		int depth=1+max(leftdepth,rightdepth); //中

		return depth;

	}

	int maxdepth(treenode* root){

		return getdepth(root);

	}

};

精简后代码：

class solution{

public:

	int maxdepth(treenode* node){

		if(root==NULL) return 0;

		retrun 1+max(maxdepth(node->left),maxdepth(node->right));

	}

};

精简之后的代码根本看不出是那种遍历方式，也看不出递归三部曲的步骤，所以如果对二叉树的操作还不熟练，尽量不奥直接按照精简代码来学。

前序代码实现

谦虚代码充分表现出求深度回溯的过程

class solution {

public:

    int result;

    void getdepth(treenode* node, int depth) {

        result = depth > result ? depth : result; // 中

        if (node->left == NULL && node->right == NULL) return ;

        if (node->left) { // 左

            depth++;    // 深度+1

            getdepth(node->left, depth);

            depth--;    // 回溯，深度-1

        }

        if (node->right) { // 右

            depth++;    // 深度+1

            getdepth(node->right, depth);

            depth--;    // 回溯，深度-1

        }

        return ;

    }

    int maxdepth(treenode* root) {

        result = 0;

        if (root == NULL) return result;

        getdepth(root, 1);

        return result;

    }

};

代码简化如下：

class solution {

public:

    int result;

    void getdepth(treenode* node, int depth) {

        result = depth > result ? depth : result; // 中

        if (node->left == NULL && node->right == NULL) return ;

        if (node->left) { // 左

            getdepth(node->left, depth + 1);

        }

        if (node->right) { // 右

            getdepth(node->right, depth + 1);

        }

        return ;

    }

    int maxdepth(treenode* root) {

        result = 0;

        if (root == 0) return result;

        getdepth(root, 1);

        return result;

    }

};

迭代法

迭代法使用层序遍历，一层一层遍历二叉树

代码如下：

class solution {

public:

    int maxdepth(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);

            }

        }

        return depth;

    }

};

559.n叉树的最大深度

题目链接：559.n叉树的最大深度

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

总体思路

和二叉树相同

递归法代码实现：

class solution {

public:

    int maxdepth(node* root) {

        if (root == 0) 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 != NULL) que.push(root);

        int depth = 0;

        while (!que.empty()) {

            int size = que.size();

            depth++; // 记录深度

            for (int i = 0; i < size; i++) {

                node* node = que.front();

                que.pop();

                for (int j = 0; j < node->children.size(); j++) {

                    if (node->children[j]) que.push(node->children[j]);

                }

            }

        }

        return depth;

    }

};

111.二叉树的最小深度

题目链接：111.二叉树的最小深度

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例:

给定二叉树 [3,9,20,null,null,15,7],返回最小深度2.

总体思路

本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。

那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离也同样是最小深度。

以下讲解中遍历顺序上依然采用后序遍历（因为要比较递归返回之后的结果，本文我也给出前序遍历的写法）。

如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。

反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

代码如下：

int leftDepth = getDepth(node->left);           // 左

int rightDepth = getDepth(node->right);         // 右

                                                // 中

// 当一个左子树为空，右不为空，这时并不是最低点

if (node->left == NULL && node->right != NULL) { 

    return 1 + rightDepth;

}   

// 当一个右子树为空，左不为空，这时并不是最低点

if (node->left != NULL && node->right == NULL) { 

    return 1 + leftDepth;

}

int result = 1 + min(leftDepth, rightDepth);

return result;

222.完全二叉树的节点个数

题目链接：222.完全二叉树的节点个数

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

输入:root = [1,2,3,4,5,6]

输出:6

普通二叉树思路

首先按照普通二叉树的逻辑来求。

这道题目的递归法和求二叉树的深度写法类似，而迭代法，二叉树：层序遍历登场！遍历模板稍稍修改一下，记录遍历的节点数量就可以了。

递归遍历的顺序依然是后序（左右中）。

递归代码实现

class solution {

public:

	int getNodeNum(TreeNode* cur){

		if(cur==NULL) return 0;

		int leftNum =getNodeNum(cur->left);

		int rightNum=genNodeNum(cur->right);

		int treeNum=leftNum+rightNum+1;

	}

public:

	class CountNodes(TreeNode* root){

		return getNodeNum(root);

	}

};

精简代码：

class solution{

public:

	int countNodes(TreeNode* root) {

        if (root == NULL) return 0;

        return 1 + countNodes(root->left) + countNodes(root->right);

    }

}

完全二叉树思路

完全二叉树

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。如图：

以下不是完全二叉树：

判断其子树是不是满二叉树，如果是则利用公式计算这个子树（满二叉树）的节点数量，如果不是则继续递归，那么在递归三部曲中，第二部：终止条件的写法应该是这样的：

if (root == nullptr) return 0;

// 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树

TreeNode* left = root->left;

TreeNode* right = root->right;

int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便

while (left) {  // 求左子树深度

    left = left->left;

    leftDepth++;

}

while (right) { // 求右子树深度

    right = right->right;

    rightDepth++;

}

if (leftDepth == rightDepth) {

    return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，返回满足满二叉树的子树节点数量

}

整体代码为

class Solution {

public:

    int countNodes(TreeNode* root) {

        if (root == nullptr) return 0;

        TreeNode* left = root->left;

        TreeNode* right = root->right;

        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便

        while (left) {  // 求左子树深度

            left = left->left;

            leftDepth++;

        }

        while (right) { // 求右子树深度

            right = right->right;

            rightDepth++;

        }

        if (leftDepth == rightDepth) {

            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0

        }

        return countNodes(root->left) + countNodes(root->right) + 1;

    }

};

补充：[C++栈使用（stack容器）](C++ stack(STL stack)用法详解 (biancheng.net))

stack

stack 容器有广泛的应用。例如，编辑器中的 undo (撤销)机制就是用堆栈来记录连续的变化。撤销操作可以取消最后一个操作，这也是发生在堆栈顶部的操作。编译器使用堆栈来解析算术表达式，当然也可以用堆栈来记录 C++ 代码的函数调用。下面展示了如何定义一个用来存放字符串对象的 stack 容器：

1.  std::stack<std::string> words;

stack 容器适配器的模板有两个参数。第一个参数是存储对象的类型，第二个参数是底层容器的类型。stack<T> 的底层容器默认是 deque<T> 容器，因此模板类型其实是 stack<typename T, typename Container=deque<T>>。通过指定第二个模板类型参数，可以使用任意类型的底层容器，只要它们支持 back()、push_back()、pop_back()、empty()、size() 这些操作。下面展示了如何定义一个使用 list<T> 的堆栈：

1.  std::stack<std::string,std::list<std::string>> fruit;

堆栈操作

和其他序列容器相比，stack 是一类存储机制简单、所提供操作较少的容器。下面是 stack 容器可以提供的一套完整操作：

top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
push(T&& obj)：以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop()：弹出栈顶元素。
size()：返回栈中元素的个数。
empty()：在栈中没有元素的情况下返回 true。
emplace()：用传入的参数调用构造函数，在栈顶生成对象。
swap(stack<T> & other_stack)：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。

代码随想录算法训练营Day16二叉树|104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

代码随想录算法训练营

代码随想录算法训练营Day16二叉树|104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

104.二叉树的最大深度

总体思路

递归法

整体代码：

前序代码实现

迭代法

代码如下：

559.n叉树的最大深度

总体思路

111.二叉树的最小深度

总体思路

222.完全二叉树的节点个数

普通二叉树思路

递归代码实现

完全二叉树思路

补充：[C++栈使用（stack容器）](C++ stack(STL stack)用法详解 (biancheng.net))

stack

堆栈操作

代码随想录算法训练营Day16二叉树|104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数的相关教程结束。

相关推荐

深度优先搜索（DFS）和广度优先搜索（BFS）

深度优先搜索（DFS）与广度优先搜索（BFS）的Java实现

深度优先搜索DFS和广度优先搜索BFS简单解析（新手向）

Leetcode之深度+广度优先搜索（DFS+BFS）专题-934. 最短的桥（Shortest Bridge）

深度优先搜索DFS和广度优先搜索BFS简单解析

代码随想录算法训练营day20 | leetcode ● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树

深度学习-05(tensorflow模型保存与加载、文件读取、图像分类：手写体识别、服饰识别)

深度解析SpringBoot内嵌Web容器