天津做网站推广的网站,网站制作理念,重庆工商大学,电商在线设计网站二叉树的递归遍历二叉树的非递归遍历写法层序遍历 递归怎么写#xff1f;
按照三要素可以保证写出正确的递归算法#xff1a;
1.确定递归函数的参数和返回值#xff1a; 确定哪些参数是递归的过程中需要处理的#xff0c;那么就在递归函数里加上这个参数#xff0c; 并且…二叉树的递归遍历二叉树的非递归遍历写法层序遍历 递归怎么写
按照三要素可以保证写出正确的递归算法
1.确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2.确定终止条件 写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。
3.确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。 前置必会
一定要会自己写出树的类定义
public class TreeNode{TreeNode left;TreeNode right;int val;TreeNode(){}TreeNode(int val){this.val val}TreeNode(int val,TreeNode right,TreeNode left){this.val val;this.left left;this.right right;
}144.二叉树的前序遍历
递归写法
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();dfs(root,result);return result;}void dfs(TreeNode root,ListInteger result){if(rootnull){return;}result.add(root.val);dfs(root.left,result);dfs(root.right,result);}}非递归写法 我认为就是记思路。 1.用一个栈作为辅助。 2.前序遍历是根左右每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。之所以是反过来是因为这样出栈的时候才是根左右的顺序。直接来看图模拟 即每次在处理根节点的时候将根节点出队然后将其右孩子先进栈再将左孩子进栈。 这样进行处理之后出栈的结果就会是前序遍历的结果。
如果还是不懂我建议直接结合代码然后结合上面图记下来这个做法。我觉得这个直接想是不好想的。
非递归其实就是用辅助数据结构配合循环
class Solution {public ListInteger preorderTraversal(TreeNode root) {//结果集ListInteger result new ArrayList();//特判if(root null){return result;}//创建辅助栈DequeTreeNode st new ArrayDeque();//根节点先入栈st.push(root);//当栈不空的时候while(!st.isEmpty()){//先处理根节点即将根节点出栈。这就对应着根TreeNode node st.pop();//将出栈的根节点加入结果集result.add(node.val);//先将右节点加入栈中可以这么想早点加入那么就晚点出。所以右节点出的时候要比左节点晚那么这里出也就是和上面节点出栈一个道理。所以这里就完成了根左右里面的根左。因为左节点进的晚出的就早。if(node.right!null){st.push(node.right);}//然后才是到左节点晚点进就可以早点出。if(node.left!null){st.push(node.left);}}return result;}
}这是我第二写总结的流程 1.初始化 创建一个空的结果列表 创建一个辅助栈 将根节点压入栈中
2.主循环 当栈不为空时执行以下操作
a. 处理当前节点 从栈中弹出一个节点 将该节点的值添加到结果列表中
b. 压入子节点 如果该节点有右子节点将右子节点压入栈中 如果该节点有左子节点将左子节点压入栈中 返回结果列表
这种方法的关键点在于 根节点最先被处理这符合前序遍历的根-左-右顺序。 右子节点先于左子节点入栈这确保了左子节点会先于右子节点被处理。 这种非递归方法的优点是
避免了递归调用的开销 对于深度很大的树可以防止栈溢出 实现简单易于理解 与中序遍历的非递归方法相比前序遍历的非递归实现更为直观因为它可以直接按照遍历顺序处理节点而不需要像中序遍历那样先到达最左节点。
145.二叉树的后序遍历
递归写法
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger result new ArrayList();dfs(root,result);return result;}public void dfs(TreeNode root,ListInteger result){if(rootnull){return;}dfs(root.left,result);dfs(root.right,result);result.add(root.val);}
}非递归写法 这个解法是一个技巧解。 由于前序遍历是根左右而后续遍历是左右根。所以如果调整一下前序遍历的顺序先加左节点再加右节点那么得到的结果就是按根右左规则得到的。所以此时做翻转那么得到的结果就是按左右根得到的结果。与后序遍历的结果不谋而合。 所以解法就是线序遍历调整左右入栈方式然后再对最终结果做翻转。
class Solution {public ListInteger postorderTraversal(TreeNode root) {DequeTreeNode st new ArrayDeque();ListInteger result new ArrayList();if(rootnull){return result;}st.push(root);while(!st.isEmpty()){TreeNode node st.pop();result.add(node.val);if(node.left!null){st.push(node.left);}if(node.right!null){st.push(node.right);}}Collections.reverse(result);return result;}
}94.二叉树的中序遍历
递归写法
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger result new ArrayList();dfs(root,result);return result;}public void dfs(TreeNode root,ListInteger result){if(rootnull){return;}dfs(root.left,result);result.add(root.val);dfs(root.right,result);}
}非递归写法 看这个图然后结合图片记下这个做法 1.初始化 创建一个空的结果列表和一个空的栈 将当前节点设置为根节点
2.主循环 当当前节点不为空或栈不为空时执行以下操作
a. 左子树遍历 如果当前节点不为空 将当前节点压入栈 移动到左子节点
b. 节点处理 如果当前节点为空即已经到达最左端 从栈中弹出一个节点 将该节点的值添加到结果列表中 将当前节点移动到右子节点
3.返回结果列表
这种方法模拟了递归的过程
首先尽可能深入地遍历左子树 然后处理节点本身 最后遍历右子树 使用栈来保存已经遍历过的父节点以便在处理完左子树后能够回溯。
还是按代码思维走一遍又和自己想的还是有一点区别。
class Solution {public ListInteger inorderTraversal(TreeNode root) {//结果集ListInteger result new ArrayList();//特判if(rootnull){return result;}//辅助栈DequeTreeNode st new ArrayDeque();//用一个遍历指针指向rootTreeNode cur root;//这里就是进递归处理的逻辑循环条件决定了能不能递归处理下去。//cur!null表明这个元素不空可以进栈!st.isEmpty()是用来回溯的表明栈中还有走过的元素需要进行处理。所以栈中走过的元素没处理完也要继续处理。while(cur!null || !st.isEmpty()){//根据中序左根右的走法需要一路向最左下走。走的过程就一直入栈保存之前的状态。如果curnull说明走到最左下的节点的左分支上了也就是null。if(cur!null){st.push(cur);cur cur.left;}else{//不能继续往左走了才处理这里这里就是开始回溯回溯一下回到最左下的节点此节点并不是null。那就把这个元素出栈把这个元素的val加入结果集。由于每个元素都要左根右这里处理了根节点那还要往右节点走。下一波显然cur还是null那么此时就会弹出沿着路线返回的根节点往后都是这样。注意是依靠弹出的节点进行转移因为栈里面的节点才是记录先前的状态别自己瞎写一个。cur st.pop();result.add(cur.val);cur cur.right;}}//当st里面为空的时候就是所有节点都处理完的时候。return result;}
}102.二叉树的层序遍历
用队列。 看一个图就懂了。 队列先进先出符合一层一层遍历的逻辑。 下面的代码就是二叉树层序遍历的模板题会这个模板之后遇到只要是层序遍历的题随便杀。
总的来说这个解法看完里面的len的处理我是当时没想到的。
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger result new ArrayList();checkFun(root,result);return result;}public void checkFun(TreeNode node,ListListInteger result){//特判if(nodenull){return;}//辅助队列DequeTreeNode que new ArrayDeque();//根节点先入队que.offerLast(node);//队列不空就代表流程还没有结束while(!que.isEmpty()){//记录一层元素的结果集ListInteger itemList new ArrayListInteger();//在一开始先记录长度该长度即队列目前的长度就是该层元素的个数。//记录len就是为了做一个界限即处理完这一层元素后就要收集一次结果集。int len que.size();//这个循环做依次将该层元素出队并扩展其左右节点加入队列当中。while(len0){//先出队TreeNode tmpNode que.pollFirst();//加入结果集itemList.add(tmpNode.val);//扩展左右节点加入队列中。if(tmpNode.left!null){que.offerLast(tmpNode.left);}if(tmpNode.right!null){que.offerLast(tmpNode.right);}//做完之后该层元素数量要-1len--;}//处理完一层后记录一次结果。result.add(itemList);}}
}107.二叉树的层序遍历Ⅱ
在上题的基础上将结果集翻转就结束了。
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {ListListInteger result new ArrayList();checkFun(root,result);Collections.reverse(result);return result;}public void checkFun(TreeNode node,ListListInteger result){if(nodenull){return;}DequeTreeNode que new ArrayDeque();que.offerLast(node);while(!que.isEmpty()){ListInteger itemList new ArrayListInteger();int len que.size();while(len0){TreeNode tmpNode que.pollFirst();itemList.add(tmpNode.val);if(tmpNode.left!null){que.offerLast(tmpNode.left);}if(tmpNode.right!null){que.offerLast(tmpNode.right);}len--;}result.add(itemList);}}
}
