LeetCode 144:二叉树的前序遍历

导读:本篇文章讲解 LeetCode 144:二叉树的前序遍历,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

二叉树的前序遍历

题目:
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

思路:
自顶向下,无值递归
在这里插入图片描述

1.前序遍历; (根左右)
先访问根结点,然后再访问左子树,最后访问右子树
2.中序遍历; (左根右) ★★★
先访问左子树,中间访问根节点,最后访问右子树
3.后序遍历; (左右根)
先访问左子树,再访问右子树,最后访问根节点

前中后序的区别只在list添加的顺序。

递归三步曲:

  1. 确定递归函数的参数和返回值:
    因为要打印出前序遍历节点的数值,所以参数里需要传入ArrayList的对象放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void(无返回值的递归)
  2. 确定终止条件:
    在递归的过程中,如何算是递归结束了呢,当然是当前遍历的节点是空了,那么本层递归就要要结束了,所以如果当前遍历的这个节点是null,就直接return
  3. 确定单层递归的逻辑:
    前序遍历是中左右的循序,所以在单层递归的逻辑,是要先添加中间根节点的数值

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

(0)
小半的头像小半

相关推荐

极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!