深圳专门网站建设,美团网站做疏通广告,封面型网页网站有哪些内容,windows下wordpress文章目录 前言1. 深入理解前中后序遍历从小到大递推分情况讨论#xff0c;明确结束条件组合出完整的方法#xff1a;从大到小 画图推演 总结 前言 提示#xff1a;没有客观公正的记忆这回事#xff0c;所有的记忆都是偏见#xff0c;都是为自己的存活而重组过的经验。--国… 文章目录 前言1. 深入理解前中后序遍历从小到大递推分情况讨论明确结束条件组合出完整的方法从大到小 画图推演 总结 前言 提示没有客观公正的记忆这回事所有的记忆都是偏见都是为自己的存活而重组过的经验。--国强生《断代》
1. 深入理解前中后序遍历
深度优先遍历有前中后序三种情况大部分人看过后就可以写出来但是很多人只是记住了代码结构稍微改变一下就废了。这就是头疼的地方。
我们再从二叉树的角度看递归每次遇到递归都是按照前面说的四步骤来写可以更好的写出正确的递归算法。通过二叉树可以非常方便的理解递归递归只是处理当前这一层和下一层之间的关系并不关系下层和下下层之间的关系就好比护犊子这个词比护孙子提起来顺口。不常用也不掺和。具体我们再强调一下着四步
从小到大递推分情况讨论明确结束条件组合出完整方法想验证则从大到小画图推演
我们接下来就一步一步看看怎么操作
从小到大递推
我们从一个二叉树为例 39 2015 6我们找一个小部分最小的子树 20 15 6假如20为head则此时前序访问顺序应该是
public void visit() {list.add(root);// 20被访问root.left; // 继续访问15root.right; // 继续访问7
}然后再往上看node(3)的情况
public void visit() {list.add(root);// 3被访问root.left; // 继续访问9root.right; // 继续访问20
}这里的20 是一个子树的父节点访问方式与上面的访问一样我们就直接把他们合并在一起
public void visit() {list.add(root);// 20被访问visit(root.left); // 继续访问15visit(root.right); // 继续访问7
}这就是我们期待的递归方法。
分情况讨论明确结束条件
上面我们已经总结出了递归的主体但是这个递归在什么时候结束呢很明显root null的时候停驶。一般来说链表和二叉树问题的终止条件都包含当前访问元素为null。有些题目结束条件复杂也是有的此时最好的方法就是
将可能结束的情况列举出来然后整理一下就可以了这个我们接着往下看。
组合出完整的方法
到目前位置我们就可以整理出完整的代码同时为了方便区分我们将方法名换成perorder:
public void perorder(TreeNode rootListInteger res) {if(root null){return ;}res.add(root.val);perorder(root.left,res); perorder(root.right,res);
}从大到小 画图推演
写完之后不要觉得就万事大吉了递归的方法很难调试的即使对的你也可能会晕这里介绍一种简单的验证方法–调用过程图法。我们可以画几个过程图看一看因为是递归函数如果比较复杂我们可以少画几组。
递归的特征是“不撞南墙不回头”一定是在执行到某个rootnull才开始返回的如下图 从图中可以看到当root的一个子树为null的时候就不会继续执行递归进入之后发现root null就看是返回了。这里要注意res.add()的时机将其进入顺序一次写出来就是我们需要的结果。该过程明确之后在debug就很容易刚开始学习递归我建议多画几次熟悉之后就不必再画图了。
前序遍历写出来之后中序和后序遍历就不是很难了中序是左中右后序时左右中。代码如下
// 中序遍历
public void inOrderRecur(TreeNode rootListInteger res) {if(root null){return ;}perorder(root.left,res); Sysytem.out.print(root.val );perorder(root.right,res);
}// 后续遍历
public void postOrderRecur(TreeNode rootListInteger res) {if(root null){return ;}perorder(root.left,res); perorder(root.right,res); Sysytem.out.print(root.val );
}另外需要注意的是
面试和力扣的上面提供的方法可能不能直接用来递归需要我们在常创建一个方法
例如144. 二叉树的前序遍历 - 力扣LeetCode 现在看到这个题目就很简单吧 public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();preorder(root,res);return res;}public static void preorder(TreeNode root, ListInteger res) {if (root null) {return;}res.add(root.val);preorder(root.left,res);preorder(root.right,res);}总结
提示图解递归二叉树递归遍历怎么写好递归
