代码随想录刷题 Day15-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录刷题 Day15。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 二叉树遍历的层序方法，记住模板后可以做下面十道题，现在暂时只做了102；

102.二叉树的层序遍历
107.二叉树的层次遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度

层序遍历的意思就是从左到右从上到下来遍历；一样的也有两种遍历手法，迭代或者递归；

迭代法需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

递归法程序和解释如下：

代码随想录刷题 Day15

注意：

- 对于二维vector取size(), 返回的是一共有几行；

- result[depth] 意思就是取到特定的二维vector的某行，然后push_back就是往这行里面输入数字；

226.翻转二叉树

这个题也可以用递归或者迭代的方法做，时间原因只掌握了递归，代码还是比较简单；

要注意翻转的是指针指向，不是node的数值；同时要注意这道题不建议用中序遍历，因为会一直对着一边的字数进行操作；迭代结束是当遍历到null节点的时候结束；

单层递归的逻辑是：

因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

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. 对称二叉树

判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。注意这个题是只能是后序遍历文章来源地址https://www.toymoban.com/news/detail-455069.html

class Solution {
public:

    bool compare(TreeNode *left, TreeNode* right){
        if(left ==NULL && right!= NULL) return false;
        else if(left !=NULL && right== NULL) return false;
        else if(left ==NULL && right== NULL) return true;
        else if(left!=NULL && right!=NULL&& left->val != right->val) return false;

        bool outside = compare(left->left, right->right);
        bool inside  = compare(left->right, right->left);
        bool result = outside &&inside;
        return result;
    }


    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return false;
        else
        return compare(root->left, root->right);
    }
};

到了这里，关于代码随想录刷题 Day15的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！