2021.4.13-2021.4.18
涉及题目为二叉树基础部分
第一周刷题结束后进行一个简单总结

其中代码详细注释见每一天的刷题笔记本总结部分只简单复现一遍代码！

题目参考开课吧某算法课程胡船长给出的内容~

题号	题名
LC144	二叉树的前序遍历
LC589	N叉树的前序遍历
LC226	翻转二叉树
剑指offer32 I	从上到下打印二叉树 I
剑指offer32 II == LC102	从上到下打印二叉树 II == 二叉树的层序遍历I
LC107	二叉树的层序遍历II
LC103	二叉树的锯齿形层序遍历

LC144 二叉树的前序遍历

解题笔记
 LC144 二叉树的前序遍历

1.题目概述

给你二叉树的根节点 root ，返回它节点值的前序遍历。
在这里插入图片描述

2.代码逻辑

【1】定义preorder函数用于进行递归接下来进行preorder函数的完成
【2】设置退出条件
【3】将“当前”节点插入结果数组的结尾
【4】遍历当前节点的左子树右子树

【5】主函数中先初始化数组然后调用preorder函数最后返回结果

3.C++代码

class Solution {
public:
	void preorder(TreeNode *root,vector<int> &res) {
		if (root == NULL) return;
        res.emplace_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
	}
    
	vector<int>preorderTraversal(TreeNode *root){
        vector<int> res;
        preorder(root, res);
        return res;
	}
};

4.python代码

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(root: TreeNode):
            if not root:
                return
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)

        res = list()
        preorder(root)
        return res

LC589 N叉树的前序遍历

解题笔记
 LC589 N叉树的前序遍历

1.题目概述

在这里插入图片描述

2.代码逻辑

整体跟二叉树的前序遍历差不多区别在于不能递归左子树+右子树而是迭代容器中所有子节点
容器就是介个~
在这里插入图片描述

1.Npreorder函数
【1】退出条件
【2】插入尾部
【3】迭代所有元素并对每个元素进行递归遍历
2.调用

3.C++代码

class Solution {
public:
    void Npreorder(Node *root, vector<int> &res){
        if(root == NULL) return;

        res.push_back(root->val);
        for(auto x: root->children){//迭代容器中所有的元素 每个元素的临时名字为x
        //一直迭代到root没有子节点为止
            Npreorder(x,res);//递归遍历
        }
    }
    vector<int> preorder(Node* root) {
        vector<int> res;
        Npreorder(root, res);
        return res;

    }
};

4.python代码

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        res = []
        def Npreorder(root):
            if root:
                res.append(root.val)
                for node in root.children:
                    Npreorder(node)
        
        Npreorder(root)
        return res

LC226 翻转二叉树

LC226 翻转二叉树
 解题笔记

1.题目概述

在这里插入图片描述

2.代码逻辑

【1】设置退出条件
【2】翻转每个节点的左子树和右子树

3.C++代码

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return root; 
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

4.python代码

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root       

        
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left, root.right = right, left 
        
        return root

剑指offer32 I 从上到下打印二叉树 I

我的解题笔记
 剑指offer32 I

1.题目概述

在这里插入图片描述

2.代码逻辑

【1】设置退出条件
如果根节点上来就是空的直接返回结果——[]
【2】初始化结果数组 ans
【3】这里与前面不同了开始！
用到了队列来暂时存储树的节点（因为需要判断什么时候结束遍历~）
所以要初始化包含根节点的队列queue = [root]

二叉树的层序遍历用队列好想一些hhh

就是这个逻辑嘛~

【3】进行BFS循环（队列queue为空时跳出循环）

1.出队：队首元素出队 TreeNode* node = q.front()
2.打印：将这个出队的元素放到结果数值末尾
3.添加子节点：node的左（右）子节点如果不为空则将左（右）子节点加入队列queue

【4】接下来来继续进行循环直到队列为空就行辽~
【5】返回打印结果数组ans

3.C++代码

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        if (root == NULL) return ans;

        queue<TreeNode*> q; //初始化队列
        q.push(root);//根入队列
        while(q.size()){
            //BFS循环
            TreeNode* node = q.front();
            q.pop();
            ans.push_back(node->val);
            if(node->left)
                q.push(node->left);
            if(node->right)
                q.push(node->right);
        }
        return ans;
    }
};

4.python代码

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root:return []
        res,queue = [],collections.deque()
        #初始化 创建空结果列表 队列
        queue.append(root) #节点入队
        while queue:
            node = queue.popleft() 
            #python可以不必把 “获取队首元素”&“队列首元素出队” 写成两句 一句解决~
            res.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        return res

剑指offer32 II 从上到下打印二叉树II == LC102 二叉树的层序遍历

我的解题笔记
 LC剑指offer32 从上到下打印二叉树II

1.题目概述

在这里插入图片描述

2.代码逻辑

C++
【1】深度优先函数的特例处理
【2】不断地往动态数组中创建新的行
【3】在每行中不断地加入每层的节点
【4】逐个节点进行递归每一个节点都进行【2】【3】操作
【5】调用时从第0层开始就ok~

python

在这里插入图片描述

3.C++代码

class Solution {
public:
    void getResult(TreeNode *root, int depth, vector<vector<int>> &ans){//深度优先搜索
        //这个是用于每一层打印结果的函数
	    if (root == NULL) return;//特例处理
	    if (depth == ans.size()) { //在当前层数与最终结果（二维动态）数组的长度相同时
            ans.push_back(vector<int>());//新建一行~
            //在二维数组没有对应”行“的时候 新建这一“行”————就这作用~
        }
	    ans[depth].push_back(root->val);//向结果数组的尾部中加入根节点
	    getResult(root->left, depth+1, ans);//逐层进行递归 
	    getResult(root->right,depth+1, ans);
        return;
        }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        getResult(root, 0, ans);//从第零层开始遍历
        return ans;
    }
};

4.python代码

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return [] #特例处理
        res, queue = [], collections.deque() #初始化队列
        queue.append(root) #把根压入队列
        while queue: #队列只要不为空 就一直循环
            tmp = [] #初始化临时列表
            for _ in range(len(queue)): #当前层打印循环
                node = queue.popleft() #队首元素出队 记为node 因为是双向队列 所以从左边出！
                tmp.append(node.val) #将node加到结果列表中
                if node.left: queue.append(node.left) #左子节点如果非空 加入队列末尾
                if node.right: queue.append(node.right) #右子节点如果非空 加入队列末尾
            res.append(tmp) #将这一层的结果打印出来 加到最后的二维结果数组中~
        return res

LC107 二叉树的层序遍历II

刷题笔记
 LC107

1.题目概述

在这里插入图片描述

2.代码逻辑

不用说了
跟LC102几乎一样诶~
C++做个翻转
在这里插入图片描述
python做个翻转。。。

3.C++代码

class Solution {
public:
    void getResult(TreeNode *root, int depth, vector<vector<int>> &ans){
	    if (root == NULL){
            return;
        }
        if(depth == ans.size()){
            ans.push_back(vector<int>());
        }
        ans[depth].push_back(root->val);
        getResult(root->left, depth+1, ans);
        getResult(root->right, depth+1, ans);
        return;
    }   
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        getResult(root, 0, ans);//先常规从上到下打印出来二维数组
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

4.python代码

这…跟LC102有啥差别
就结尾返回ans[::-1]）（翻转结果数组）就行了
这就便捷得一批~

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root: return [];
        ans,queue=[],collections.deque()
        queue.append(root)
        while queue:
            tmp = []
            for _  in range(len(queue)):
                node = queue.popleft()#队首元素出队 因为是双向队列 所以从左边出！
                tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            ans.append(tmp)
        return ans[::-1]

LC103 二叉树的锯齿形层序遍历

超级nice的一道题！
这题的刷题笔记记录了好多东西！
感觉前面刷了这么多二叉树相关的基础题
在这道题上都汇总起来了~
我的刷题笔记
 LC103 二叉树的锯齿形层序遍历

1.题目概述

在这里插入图片描述

2.代码逻辑

依旧是熟悉的层序遍历
只不过变了下方向

C++
【1】定义总队列装全部节点
【2】定义变量isOrderLeft 记录是否从左到右插入
【3】进入循环循环终止条件为总队列为空
【4】循环中定义一个双端队列 levelList来存储当前层的值
【5】遍历当前层的值并将所有值出队之后将这些出队的值存入双端队列（如果isOrderLeft 为True就从左向右插入为False就从右向左插入）
【6】将【4】【5】两步得到的当前层的结果添加到结果数组中
【7】（还在循环中嗷）做isOrderLeft = !isOrderLeft 操作达到“偶数层反向遍历”的效果
【8】跳出循环输出结果

python
取巧了23333 直接层序遍历加上指定层数翻转
【1】层序遍历
在这里插入图片描述

【2】指定层数（偶数层）翻转遍历结果数组（就是那个每层的一维结果数组啦）
在这里插入图片描述

3.C++代码

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;

        //利用队列实现 BFS按层遍历
        queue<TreeNode*> nodeQueue;//定义一个TreeNode*类的队列 nodeQueue（这个解释不太清楚准不准确 是暂时的一个认知）
        nodeQueue.push(root);
        bool isOrderLeft = true;//记录是否是从左到右插入(true)

        while (!nodeQueue.empty()){
            //如果队列不为空 就一直循环下去
            deque<int> levelList;//定义一个双端队列levelList来存储当层的值   
            int size = nodeQueue.size();//size存储了当前层的长度 方便下面对队列进行遍历
            for (int i=0; i < size; i++){//遍历总队列中该层的值并将所有值出队  按标志位存入双端队列 再按固定顺序读取下一层节点值进队列
                auto node = nodeQueue.front();//取出队列第一个值 存储到node中
                nodeQueue.pop();
                if(isOrderLeft) {//奇数层 从左到右插入双端队列
                    levelList.emplace_back(node->val);
                }
                else{
                    levelList.push_front(node->val);//从容器开头开始插入元素 实现从左往右插入双端队列
                }

                //接下来读取下一层节点值进入双端队列
                if(node->left){
                    nodeQueue.push(node->left);//左子节点不为空 就插到总队列中
                }
                if(node->right){
                    nodeQueue.push(node->right);
                }
            }
            ans.emplace_back(vector<int>{levelList.begin(),levelList.end()});
            //将当前层的值添加到结果数组中
            //前面的vector<int>将队列格式转换格式
            isOrderLeft = !isOrderLeft;
        }
    return ans;
    }
};

4.python代码

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        #先层序遍历 再把偶数层的结果翻转即可~
        stack = [root]#总队列 遍历的树暂时都装这里
        ans = []
        while stack:
            level = [] #存储每一层用的队列 其结果直接扔到ans结果数组中
            for _ in range(len(stack)):
                node = stack.pop(0)
                if not node:
                    continue
                level.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
            if level:
                ans.append(level)
        for i in range(1, len(ans), 2):#从1到结果数组的长度 步长为2 
            ans[i] = ans[i][::-1] #[::-1]是翻转数组的意思 
            #把ans[i]这个数组翻转过来
        return ans

4 二叉树基础——第一周力扣C++ python每日一题总结

文章目录

LC144 二叉树的前序遍历

1.题目概述

2.代码逻辑

3.C++代码

4.python代码

LC589 N叉树的前序遍历

1.题目概述

2.代码逻辑

3.C++代码

4.python代码

LC226 翻转二叉树

1.题目概述

2.代码逻辑

3.C++代码

4.python代码

剑指offer32 I 从上到下打印二叉树 I

1.题目概述

2.代码逻辑

3.C++代码

4.python代码

剑指offer32 II 从上到下打印二叉树II == LC102 二叉树的层序遍历

1.题目概述

2.代码逻辑

3.C++代码

4.python代码

LC107 二叉树的层序遍历II

1.题目概述

2.代码逻辑

3.C++代码

4.python代码

LC103 二叉树的锯齿形层序遍历

1.题目概述

2.代码逻辑

3.C++代码

4.python代码