题目:
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
1.前序遍历; (根左右)
先访问根结点,然后再访问左子树,最后访问右子树
2.中序遍历; (左根右) ★★★
先访问左子树,中间访问根节点,最后访问右子树
3.后序遍历; (左右根)
先访问左子树,再访问右子树,最后访问根节点
前中后序的区别只在list添加的顺序。
递归三步曲:
- 确定递归函数的参数和返回值:
因为要打印出前序遍历节点的数值,所以参数里需要传入ArrayList的对象放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void(无返回值的递归) - 确定终止条件:
在递归的过程中,如何算是递归结束了呢,当然是当前遍历的节点是空了,那么本层递归就要要结束了,所以如果当前遍历的这个节点是null,就直接return - 确定单层递归的逻辑:
前序遍历是中左右的循序,所以在单层递归的逻辑,是要先添加中间根节点的数值
class Solution {
List<Integer> r; // 声明成员变量
public List<Integer> preorderTraversal(TreeNode root) {
r=new ArrayList<>(); // 在方法内实例化
pre(root);
return r;
}
public void pre(TreeNode root){
if(root==null){
return;
}
//
r.add(root.val); //前序
pre(root.left);
pre(root.right);
}
}
总结:
前序位置是刚刚进入节点的时刻,后序位置是即将离开节点的时刻。
但这里面大有玄妙,意味着前序位置的代码只能从函数参数中获取父节点传递来的数据,而后序位置的代码不仅可以获取参数数据,还可以获取到子树通过函数返回值传递回来的数据。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/89334.html