[LeetCode力扣hot100]-二叉树相关手撕题

简单 94.中序遍历

就说左子树-根-右子树顺序，之前也有二叉树相关的文章，基本上递归为主，这里用栈等方式实现下。

用到：栈

注意上面给出节点的基本结构，如左右，val指等

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; //最后输出需要vector形式 stack<TreeNode*> stk; //借助栈 while(root||!stk.empty()){ while(root){ //塞满左边 stk.push(root); root=root->left; } //往下翻存数，直到翻到右边 root=stk.top(); stk.pop(); res.push_back(root->val); root=root->right; } return res; } }; 104.二叉树最大深度

递归即可，max（左子树深度，右子树深度）+1；

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

 基于这道题,引申下面这道题：

二叉树的直径

543. 二叉树的直径 - 力扣（LeetCode）必须掌握上一题深度的写法，得到每个节点作为根节点的最大深度，同时记录其左右最大深度。

class Solution { public: int max1=0; int Deep(TreeNode* root) { if(root==nullptr){ return 0; } int left1= Deep(root->left); int right1=Deep(root->right); max1=max(max1,left1+right1); return max(left1,right1)+1; } int diameterOfBinaryTree(TreeNode* root) { if(root==nullptr){ return 0; } Deep(root); return max1; } }; 226。翻转二叉树 

226.翻转二叉树

也是递归

class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==nullptr){ return nullptr; } TreeNode* left=invertTree(root->left); TreeNode* right=invertTree(root->right); root->left=right; root->right=left; return root; } }; 101.对称二叉树

要自己写个函数，再递归

class Solution { public: bool pan(TreeNode* t1,TreeNode* t2){ //自己写的函数 if(t1==nullptr&&t2==nullptr){ return true; }else if(t1==nullptr || t2==nullptr){ return false; }else{ return t1->val==t2->val &&pan(t1->left,t2->right)&&pan(t1->right,t2->left); } } bool isSymmetric(TreeNode* root) {//题目给的 return pan(root,root); } }; 二叉树的直径 

543. 二叉树的直径 - 力扣（LeetCode）

中等

0927面试了某家中厂，考到二叉树层级遍历了，很悲催的没有做出来，在此反思复习一下。

树的递归——类似于图的深搜。

树的层级遍历——类似于图的广搜。

1.二叉树的层级遍历

. - 力扣（LeetCode）注意，这个q.size()是在不断变化的，if(current2->left/right)处理时，不断往q队列里塞入当前节点的左右节点，注意就不用else处理了。最后打印二维数组即可

借助数据结构：queue

class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if(!root){ return result; }//为空处理 queue<TreeNode*> q; q.push(root); while(!q.empty()){ int levelSize=q.size(); vector<int> current1;//层级 for(int i=0;i<levelSize;++i){ TreeNode *current2=q.front();//单个节点 q.pop(); current1.push_back(current2->val); if(current2->left){ q.push(current2->left); } if(current2->right){ q.push(current2->right); } } result.push_back(current1); } return result; } };