给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

迭代我们需要准备一个stack容器sta来存放节点以保证能回溯，一个vector容器v来存储结果。先判断给的树root是否为空，如果为空就直接把v返回给他结束程序，如果root不为空我们就开始遍历，用while来遍历root，只要root不为NULL或sta.size()不为0就一直循环下去，while里再套入一个while，只要root不为空就一直在这个while里，每次遍历把当前节点存入sta中，把节点的val存入v中，然后root=root->left一直遍历下去。当内部的while结束时说明当前节点为空了，也就说明它的父节点没有左节点，我们把存在sta中的父节点取出赋给root，同时顶端元素出栈，把现在节点的val值存入v中，然后让当前节点往right的方向走，然后回到最开始的地方进行下一次迭代。最后迭代结束后v里就是我们要的前序遍历，返回v即可。

/*** 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> preorderTraversal(TreeNode* root) {vector<int>v;if(!root)return v;stack<TreeNode*>sta;while(sta.size()||root){while(root){v.push_back(root->val);sta.push(root);root=root->left;}root=sta.top();sta.pop();root=root->right;}return v;}
};

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

中序遍历和前序遍历的大体步骤一样，但是while循环里的操作顺序略有不同，在while的嵌套while中，我们不往v中存节点的val值，只把节点存入sta中，然后一直往left遍历，当嵌套while结束时说明当前节点的父节点没有左节点，我们把sta的顶端元素（即父节点）赋给root，同时把顶端元素弹出，然后把当前节点的val存入v中，再把节点向right方向走，回到开头处继续迭代。最后返回v。

/*** 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>v;if(!root)return v;stack<TreeNode*>sta;while(sta.size()||root){while(root){sta.push(root);root=root->left;}root=sta.top();sta.pop();v.push_back(root->val);root=root->right;}return v;}
};

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [3,2,1]

和前面的中序遍历也是大同小异，但我们这里事先准备的不止v和sta，还要准备一个树节点p，初始指向NULL,然后开始遍历，嵌套的while和中序遍历一样，只存节点在sta里，然后节点一直往left走，嵌套的while结束说明当前节点的父节点没有左子树，我们从sta中取出并弹出顶端元素给root，然后判断一下，现在root的right是否等于NULL或等于p，如果满足一点，那么我们把当前节点的val存入v中，并把当前节点赋给p，然后令当前节点变为NULL；如果不满足任意一点，那么我们就把当前节点在存回sta中，并让节点向right方向走。然后回到开头继续迭代，最后返回v。

/*** 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> postorderTraversal(TreeNode* root) {vector<int>v;if(!root)return v;stack<TreeNode*>sta;TreeNode*p=NULL;while(sta.size()||root){while(root){sta.push(root);root=root->left;}root=sta.top();sta.pop();if(!root->right||root->right==p){v.push_back(root->val);p=root;root=NULL;}else{sta.push(root);root=root->right;}}return v;}
};

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

示例 1：

输入：root = [1,2,3,4], x = 4, y = 3
输出：false

堂兄弟的定义是：深度一样，父节点不一样。所以我们准备两个全局map容器father和mymap（不全局也可以，但dfs传参要多加这两个容器）来分别存放父节点和深度，我们用dfs函数来遍历树，dfs有五个参数，一个是当当前节点，一个是当前节点的子节点（左节点或右节点），一个是深度u（初始为0），还有两个是x和y。dfs一开始先判断当前节点是否为空，如果是就直接结束程序，如果不是就判断节点的val值等不等于x或y，如果等于就用mymap函数存下这个节点的深度u，再用father存下节点的父节点。然后我们把当前节点的左节点和右节点接着送去递归。当一切结束后，我们判断两个节点x和y的深度是否相等，如果相等判断他俩的父节点是否为同一个，如果为同一个即不是堂兄弟，如果不是则是堂兄弟。

/*** 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:unordered_map<int,int>mymap;unordered_map<int,int>father;bool isCousins(TreeNode* root, int x, int y) {TreeNode* t;t=new TreeNode(200);dfs(root,x,y,0,t);if(mymap[x]==mymap[y]&&father[x]!=father[y]){return true;}return false;}void dfs(TreeNode* p,int x,int y,int u,TreeNode* q){if(mymap.size()==2)return;if(!p)return;if(p->val==x){mymap[x]=u;father[x]=q->val;}else if(p->val==y){mymap[y]=u;father[y]=q->val;}dfs(p->left,x,y,u+1,p);dfs(p->right,x,y,u+1,p);}
};

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

准备一个全局vector容器v来存放节点，注意是存节点而不是val值，不喜欢全局变量的话dfs的参数要把v也传过去比较麻烦我就直接全局设定了。之前我们写过递归求前序遍历的方法拿到这里来也是通用的，当我们把前序排序的结果存在v里后，我们把根节点的left和right都指向NULL，然后用for遍历，i=1(因为根节点已经是v[0]了)，每次把根节点的right指向v[i]，然后把root往right上走一格，注意要把left都指向NULL。最后遍历完要把最后一个节点的right指向NULL。

/*** 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<TreeNode*>v;void dfs(TreeNode* root){if (!root)return;else{v.push_back(root);dfs(root->left);dfs(root->right);}}void flatten(TreeNode* root) {if (!root)return;dfs(root);root->left = NULL;root->right = NULL;int n = v.size();for (int i = 1; i < n; i++){root->right = v[i];root = root->right;root->left=NULL;}root->right = NULL;}
};

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

示例 1：

输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true

这回没法用全局vector容器了，因为这次有两个v，如果用全局系统不知道把值插入哪个地方，所以这次老老实实传v做参数吧。

准备两个vector容器v1和v2，分别存root1和root2的叶子节点，我们实现一个dfs函数（这里我们采用的是前序遍历的方法），传入树节点root和vector容器做参数，每次先判断当前节点是否为空，如果为空就结束程序，如果不为空就判断当前节点有没有子节点（left和right）如果没有就说明这个是一个叶节点，我们把这个节点的val值存入v中，并结束程序。如果这个节点不是叶子节点，那我们就把当前节点的left和right分别送去递归。当递归完后v1和v2就存好了两个数的叶子节点，先判断两个v所存元素个数是否相等，如果不相等就直接返回false，如果相等再一个个比较元素，如果有不一样的就返回false。如果都一样就返回true。

/*** 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:bool leafSimilar(TreeNode* root1, TreeNode* root2) {vector<int>v1;vector<int>v2;dfs(root1,v1);dfs(root2,v2);int n=v1.size(),m=v2.size();if(n!=m)return false;for(int i=0;i<n;i++){if(v1[i]!=v2[i])return false;}return true;}void dfs(TreeNode* root,vector<int>&v){if(!root)return;else if(!root->left&&!root->right){v.push_back(root->val);return;}dfs(root->left,v);dfs(root->right,v);}
};