Junyuan's Homepage

226. 翻转二叉树

题目链接：click here
文章讲解：click here
题目描述：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
思路：
其实就是遍历这棵树，然后反转每个节点的左右子节点

注意，已经反转过的了不能再被反转，所以用中序遍历不太合适，因为左子树反转后，反转根节点，再反转右子树的时候，本质上还是反转的刚刚那个左子树。

具体做法：
1. 层序遍历，处理每个节点时，反转其左右子树，再将反转后的左右子树压入队列
2. 前序遍历，递归实现，中左右，中则反转其左右子树，左和右则递归调用函数

层序遍历代码：

class Solution
{
public:
    TreeNode *invertTree(TreeNode *root)
    {
        queue<TreeNode *> qt;
        if (root)
            qt.push(root);

        while (!qt.empty())
        {
            int size = qt.size();

            for (int i = 0; i < size; i++)
            {
                auto cur = qt.front();
                auto temp = cur->left;
                cur->left = cur->right;
                cur->right = temp;

                qt.pop();
                if (cur->left)
                    qt.push(cur->left);
                if (cur->right)
                    qt.push(cur->right);
            }
        }

        return root;
    }
};

前序遍历代码：更简洁，优先掌握

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        return root;
    }
};

101. 对称二叉树

题目链接：click here
文章讲解：click here
题目描述：使用迭代法完成二叉树的前中后序遍历
思路：
关键是想到对比两个子树的根、左侧、右侧是否相等，所以本质上是同时对两颗子树进行前序遍历，我不认为是如讲解中注释的后序遍历

具体做法是，从根节点开始，比较左右两颗子树是否对称，进递归函数

递归函数传参及返回：传入左右两个节点，传出二者是否相等

递归函数终止：什么时候能返回确定的 bool 结果呢？就是传入的左右节点触及NULL的时候
1. 左null, 右null，返回true
2. !左null, 右null，返回false
3. 左null, !右null，返回false
4. !左null, !右null，但二者值不相同,返回false
递归内逻辑：如果还不能由当前的两个根节点（就是传入的左、右指针）完成判断，则进入对下一层的判断
1. 递归调用(左->左，右->右)，看外侧是否相等
2. 递归调用(左->右，右->左)，看内测是否相等
3. 返回上述结果的与。
注意，这里面传入参数的前后顺序千万不能反，一者始终在中轴线左，零一者始终在其右。

递归遍历代码：

class Solution
{
public:
    bool cmp(TreeNode *left, TreeNode *right)
    {
        if (!left && right)
        {
            return false;
        }
        else if (left && !right)
        {
            return false;
        }
        else if (!left && !right)
        {
            return true;
        }
        else if (left->val != right->val)
        {
            return false;
        }

        // 到这里就隐含了 left->val == right->val                    //mid
        bool outside = cmp(left->left, right->right); // left
        bool inside = cmp(left->right, right->left);  // right
        bool is_same = outside && inside;

        return is_same;
    }

    bool isSymmetric(TreeNode *root)
    {
        return cmp(root->left, root->right);
    }
};

迭代法代码：一样的思路，中左右，中用于判断，左右用于将数据压入栈，后续循环中验证下一层。只要有一处false，就可以返回false了。

class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {
        if (!root)
            return true;

        stack<TreeNode *> st;
        st.push(root->left);
        st.push(root->right);

        while (!st.empty())
        {
            auto right = st.top();
            st.pop();
            auto left = st.top();
            st.pop();

            if (!right && !left)
            {
                continue;
            }

            if (!right || !left || right->val != left->val)
            {
                return false;
            }

            st.push(left->left);
            st.push(right->right);

            st.push(left->right);
            st.push(right->left);
        }

        return true;
    }
};

104. 二叉树的最大深度

题目链接：click here
文章讲解：click here
题目描述：给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
思路：
昨天做完层序遍历后练过这道题，所以迭代法可以就用层序遍历，数了有多少层，最大深度就是多少。
关于递归法，可以用任意一种顺序的递归，递归时候要把深度值传入，并且需要和当前保存的最大深度进行对比，取大的那个，赋值给最大深度。
进阶的N叉数的最大深度，用层序遍历和前序遍历时，代码只需要把遍历左、右子树换成遍历子树vector即可。

迭代代码：

class Solution
{
public:
    int maxDepth(TreeNode *root)
    {
        int res = 0;
        queue<TreeNode *> qt;
        if (root)
            qt.push(root);

        while (!qt.empty())
        {
            res++;
            int size = qt.size();
            for (int i = 0; i < size; i++)
            {
                auto x = qt.front();
                if (x->left)
                    qt.push(x->left);
                if (x->right)
                    qt.push(x->right);
                qt.pop();
            }
        }
        return res;
    }
};

递归代码：前序根左右，根统计深度（递增）、左右递归到下一层，最终就是看最远的根有多深

class Solution
{
public:
    void order(TreeNode *cur, int &res, int depth)
    {
        if (!cur)
            return;

        if (res == depth)
            res++;

        order(cur->left, res, depth + 1);
        order(cur->right, res, depth + 1);
    }

    int maxDepth(TreeNode *root)
    {
        int res = 0;
        order(root, res, 0);
        return res;
    }
};

递归代码：后序：本质上也是先搜到底层，在递归函数栈归的过程中，累加高度值，形成深度值
若本层为null, 返回高度0
左右子树的高度，取大者再+1即为本节点的高度。

class Solution
{
public:
    int order(TreeNode *cur)
    {
        if (!cur)
            return 0;

        int height1 = order(cur->left);
        int height2 = order(cur->right);

        int max = height1 > height2 ? height1 : height2;
        return max + 1;
    }

    int maxDepth(TreeNode *root)
    {
        return order(root);
    }
};

111. 二叉树的最小深度

题目链接：click here
文章讲解：click here
题目描述：给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
思路：
这里也是层序遍历昨天解过，和上面的区别在于，需要有一个中途退出的逻辑，即遍历本层节点时，若某个节点同时没有左、右子节点，则可退出，输出最小深度

迭代代码：

class Solution
{
public:
    int minDepth(TreeNode *root)
    {
        int res = 0;
        queue<TreeNode *> qt;
        if (root)
            qt.push(root);

        while (!qt.empty())
        {
            res++;
            int size = qt.size();
            for (int i = 0; i < size; i++)
            {
                auto x = qt.front();
                // 中途退出逻辑
                if (!x->left && !x->right)
                {
                    return res;
                }
                if (x->left)
                    qt.push(x->left);
                if (x->right)
                    qt.push(x->right);
                qt.pop();
            }
        }
        return res;
    }
};

递归代码：前序：本质上是先搜到底层，在递的过程中传递深度值，在递归函数栈归的过程中，检索最小深度在哪儿【根的左右均为空】

class Solution
{
private:
    int res = INT_MAX;

public:
    void order(TreeNode *cur, int depth)
    {

        if (!cur)
        {
            return; // mid
        }

        if (!(cur->left) && !(cur->right))
        {
            res = min(res, depth + 1); // mid
        }

        if (cur->left)
        {
            order(cur->left, depth + 1); // left
        }
        if (cur->right)
        {
            order(cur->right, depth + 1); // right
        }
    }

    int minDepth(TreeNode *root)
    {
        if (!root)
            return 0;
        order(root, 0);
        return res;
    }
};

递归代码：后序：本质上也是先搜到底层，在递归函数栈归的过程中，累加高度值，形成深度值
并且若左右子树均非空，本层深度取左右子树深度的小者+1，
若二者全空，本层深度为1，
若其中一方空，本层深度为另一方深度+1.

class Solution
{
public:
    int order(TreeNode *cur)
    {

        if (!cur)
        {
            return 0;
        }

        int height1 = order(cur->left); // 左
        int height2 = order(cur->right); // 右

        // 中：
        if (height1 == 0 && height2 == 0)
        {
            return 1;
        }
        else if (height1 == 0 && height2 != 0)
        {
            return 1 + height2;
        }
        else if (height1 != 0 && height2 == 0)
        {
            return 1 + height1;
        }

        int min = height1 > height2 ? height2 : height1;

        return min + 1;
    }

    int minDepth(TreeNode *root)
    {
        return order(root);
    }
};

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
今日核心思想：夹带着遍历二叉树完成各种特殊任务

翻转二叉树：本质上就是遍历然后反转左右子树，前序和层序较为简单，优先掌握递归前序法

对称二叉树：需要设计双树并行遍历，每次比对双树的对称位置的元素是否一致；递归和迭代都要注意要同时比当前节点与对比节点的根，外侧和内侧是否全一致，不一致就可返回false

二叉树的最大深度：层序和前序遍历比较简单，后序本质上是从下往上累计高度，最终得到根节点的深度

二叉树的最小深度：同样是层序和前序遍历简单，后序本质上是从下往上累计高度，最终得到根节点的深度

只不过最大、最小深度里，后序的高度累计方法不一样。
耗时：2h

Junyuan Lu(陆俊元)

代码随想录算法训练营第十四天 | 226. 翻转二叉树、101. 对称二叉树、104. 二叉树的最大深度、111. 二叉树的最小深度

226. 翻转二叉树

101. 对称二叉树

104. 二叉树的最大深度

111. 二叉树的最小深度

今日收获