vi设计案例网站,12个优秀的平面设计素材网站,阿里云网站备案多少天,电商运营视频教程层序遍历
层序遍历一个二叉树#xff0c;就是从左往右一层一层的遍历二叉树#xff0c;这种遍历方式需要借用一个辅助数据结构即队列来实现#xff0c;队列先进先出#xff0c;符合一层一层遍历的逻辑#xff0c;而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而…层序遍历
层序遍历一个二叉树就是从左往右一层一层的遍历二叉树这种遍历方式需要借用一个辅助数据结构即队列来实现队列先进先出符合一层一层遍历的逻辑而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历只不过我们用在二叉树上。
使用队列实现二叉树广度优先遍历。
class Solution{
public:vectorvectorintlevelOrder(TreeNode* root){queueTreeNode*que;if(root ! NULL)que.push(root);vectorvectorintresult;while(!que.empty()){int size que.size();vectorintvec;//这里使用固定大小size,不要使用que.size().因为que.size是不断变化的for(int i 0;i size; i){TreeNode* node que.front();que.pop();vec.push_back(node-val);if(node-left)que.push(node-left);if(node-right)que.push(node-right);}result.push_back(vec);}return result;}
};
//递归法
class Solution{
public:vod order(TreeNode* cur,vectorvectorintresult,int depth){if(cur nullptr)return;if(result.size() depth)result.push_back(vectorint());result[depth].push_back(cur-val);order(cur-left,result,depth 1);order(cur-right,result,depth 1);}vecctorvectorintlevelOrder(TreeNode* root){vectorvectorintresult;int depth 0;order(root,result,depth);return result;}
};
反转二叉树
思路只要把每个节点的左右孩子翻转一下就可以达到整体翻转的效果。这道题使用前序遍历和后序遍历都可以唯独中序遍历不方便因为中序遍历会把某些节点的左右孩子翻转两次。层序遍历也可以。
递归三步
1.确定递归函数的参数和返回值
参数就是要传入节点的指针不需要其他参数了通常此时定下来主要参数如果在写递归的逻辑中发现还需要其他参数的时候随时补充。
返回值的话其实也不需要但是题目中给出的要返回root节点的指针可以直接使用题目定义好的函数所以就函数的返回类型TreeNode*。
TreeNode* invertTree(TreeNode* root)
2.确定终止条件
当前节点为空的时候就返回
if(root NULL)return root;
3.确定单层递归的逻辑
因为先前序遍历所以先进行交换左右孩子节点然后左转左子树反转右子树。
swap(root-left,root-right);
invertTree(root-left);
invertTree(root-right);
//基于上面三步完整C代码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;}
};
迭代法 深度优先遍历
前序遍历
class Solution{TreeNode* invertTree(TreeNode* root){if(root NULL)retrun root;stackTreeNode*st;st.push(root);while(!st.empty()){TreeNode* node st.top(); //中st.pop();swap(node-left,node-right);if(node-right)st.push(node-right); //右if(node-left)st.push(node-left); //左}return root;}
};
前序遍历
class Solution{
public:TreeNode* invertTree(TreeNode* root){stackTreeNode*st;if(root ! NULL)st.push(root);//判断非空栈尾部添加元素while(!st.empty()){TreeNode* node st.top(); //top()取出栈顶元素if(node ! NULL){st.pop(); //pop()删除栈顶元素if(node-right)st.push(node-right);//右if(node-left)st.push(node-left);//左st.push(node);st.push(NULL); //中}else{st.pop();node st.top();st.pop();swap(node-left,node-right); //节点处理逻辑}}return root}
}
广度优先遍历
//层序遍历可以翻转这棵树因为层序遍历也可以把每个节点的左右孩子都翻转一遍代码如下
class Solution{
public:TreeNode* invertTree(TreeNode* root){queueTreeNode*que;if(root ! NULL)que.push(root);while(!que.empyu()){int size que.size();for(int i 0;i size;i){TreeNode* node que.front();que.pop();swap(node-left,node-right);//节点处理左右交换if(node-left)que.push(node-left);if(node-right)que.push(node-right);}}return root;}
};
不能用递归的中序遍历因为使用递归的中序遍历某些节点的左右孩子会翻转两次。
但也可以避免。
class Solution{
public:TreeNode* invertTree(TreeNode* root){if(root NULL)return root;invertTree(root-left); //左swap(root-left,root-right); //中invertTree(root-left);//注意这里仍然要遍历左孩子因为中间节点已经翻转了return root;}
}
但这不算真正的递归中序遍历了。
但使用迭代方式统一写法的中序遍历是可以的。
class Solution{
public:
TreeNode* invertTree(TreeNode* root){stackTreeNode*st;if(root ! NULL)st.push(root);while(!st.empty()){TreeNode* node st.top();if(node ! NULL){st.pop();if(node-right)st.push(node-right);//右st.push(node);//中st.push(NULL);if(node-left)st.push(node-left);//左}else{st.pop();node st.top();st.pop();swap(node-left,node-right); //节点处理逻辑}}return root;
}
};
上面是用栈来遍历而不是用指针避免了递归法中翻转了两次的情况。 总结对于二叉树的问题解题前想清楚究竟是前中后序遍历还是层序遍历。
对称二叉树
判断对称二叉树要比较的是哪两个节点要比较的不是左右节点而是两个树这个树是根节点的左右子树所以在递归遍历的过程中也要同时遍历两棵树。
如何比较比较两个子树的里侧和外侧元素是否相等。
遍历的顺序只能是“后序遍历”因为我们要通过递归函数的返回值来判断两个子树的内测节点和外侧节点是否相等。
正是因为要遍历两棵树而且要比较内侧和外侧节点所以准确的来说是一个树的遍历顺序是左右中一个树的遍历顺序是右左中。
但都可以理解算是后序遍历尽管已经不是严格上在一个树上进行遍历的后序遍历了。
后序可以理解为一种回溯
递归法
递归三部曲
1.确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的进而判断这个树是不是对称树所以要比较的是两个树参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。
代码如下
bool comppare(TreeNode* left,TreeNode* right)
2.确定终止条件
要比较两个节点数值相不相同首先要把两个节点为空的情况弄清楚否则后面比较数值的时候就会操作空指针了。
节点为空的情况有注意比较的是左右节点是节点不是左右孩子
左节点为空右节点不为空不对称return false
左不为空右为空不对称return false
左右都为空对称返回true
此时已经排除掉了节点为空的情况那么剩下的就是左右节点不为空
左右节点都不为空比较节点数值不相同就return false
此时左右节点不为空且数值也不相同的情况我们也处理了。
代码如下
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-val ! right-val)return false;
注意最后一种情况没用else 而是else if,因为我们把以上情况都排除之后剩下的就是左右节点都不为空且数值相同的情况。
3.确定单层递归的逻辑
此时才进入单层递归的逻辑层递归的逻辑就是处理 左右节点都不为空且数值相同的情
比较二叉树外侧是否对称传入的是左节点的左孩子右节点的右孩子。
比较内侧是否对称传入左节点的右孩子右节点的左孩子。
比较内侧是否对称传入左节点的右孩子右节点的左孩子。
如果左右都对称就返回true,有一侧不对称就返回false.
bool outside compare(left-left,right-right)//左子树左、右子树;右
bool inside compare(left-right,right-left);//左子树右、右子树左
bool isSame outside inside; //左子树中、 右子树中逻辑处理
retrun isSame;
如上代码中我们可以看出使用的遍历方式左子树左右中右子树右左中所以也叫做“后序遍历尽管不是严格的后序遍历。
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-val ! right-val)return false;//此时就是左右节点都不为空且数值相同的情况//此时才做递归做下一层的判断bool outside compare(left-left,right-right);//左子树左、 右子树右bool inside compare(left-right,right-left); //左子树右、 右子树:左bool isSame outside inside; //左子树中、右子树中逻辑处理return isSame;}bool isSymmetric(TreeNode* root){if(root NULL)return true;return compare (root-left,root-right);}
}; 迭代法
翻转二叉树也可以使用迭代法但要注意这里迭代法不是前中后序的迭代写法因为本题的本质是判断两个树是否是相互翻转的其实已经不是所谓二叉树遍历的前中后序的关系了。
这里我们可以使用队列来比较两个树根节点左右子树是否相互翻转注意这不是层序遍历
使用队列
通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等
class Solution{
public:bool isSymmetric(TreeNode* root){if(root NULL)return true;queueTreeNode*que;que.push(root-left);//将左子树节点加入队列que.push(root-right);//将右子树头节点加入队列while(!que.empty()){//接下来就要判断这两个树是否相互翻转TreeNode* leftNode que.front();que.pop();TreeNode* rightNode que.front();que.pop();if(!leftNode !rightNode){//左节点为空右节点为空此时说明是对称的continue;}//左右一个节点不为空或者都不为空但数值不相同返回falseif((!leftNode || rightNode || (leftNode-val ! rightNode-val))){return false;}que.push(leftNode-left);//加入左节点左孩子que.push(rightNode-right);//加入右节点右孩子que.push(leftNode-right);//加入左节点右孩子que.push(rightNode-left);//加入右节点左孩子}return true;}
}; 使用栈
把左右子树要比较的元素放进一个容器然后成对的取出来进行比较那么其实使用栈也是可以的。
只要把队列原封不动的改成栈就可以了
class Solution{
public:bool isSymmetric(TreeNode* root){if(root NULL)return true;stackTreeNode*st;//这里改成了栈st.push(root-left);st.push(root-right);while(!st.empty()){TreeNode* leftNode st.top();st.pop();TreeNode* rightNode st.top();pop();if(!leftNode !rightNode){continue;}if ((!leftNode || rightNode || (leftNode-val ! rightNode - val))){return false;}st.push(leftNode-left);st.push(rightNode-right);st.push(leftNode-right);st.oush(rightNode-left);}return true;}
};
