您的位置 首页 java

二叉树的遍历(左中右及层级)

大家好,我是热心的大肚皮,皮哥。以后我们又多了一个 算法 系列,会带着大家一起向着成神之路迈进。

什么是 二叉树

简单介绍下,二叉树是 一种典型的树状结构。如它名字所描述的那样,二叉树是每个节点最多有 两个子树 的树结构,通常子树被称作“左子树”和“右子树”。如下图。

最好情况下的算法时间复杂度为O(1),最坏情况下的算法时间复杂度为O(n)。

二叉树如何遍历?

二叉树的基本遍历方式有4种,即前序遍历、 中序遍历 、后序遍历以及层序遍历。

  • 前序遍历

按照根节点 -> 左孩子 -> 右孩子 的方式遍历,每次先遍历根节点,遍历结果为 1 2 4 5 3 6 7 ;直接上代码。

 public List<Integer> preorderTraversal(TreeNode  root ) {
    List<Integer> list = new ArrayList<>();
    getNodeVal(list, root);
    return list;
}
public  void  getNodeVal(List<Integer> list, TreeNode root){
    //如果没有节点直接返回
    if (null == root){
        return;
    }
    //前序遍历先添加 根->左->右 ,所以先添加根的值
    list.add(root.val);
    //递归查询先添加左节点
    getNodeVal(list, root.left);
    //递归查询先添加右节点
    getNodeVal(list, root.right);
}  

  • 中序遍历

按照 左孩子-> 根节点 -> 右孩子 的方式遍历,每次先遍历左孩子,遍历结果为 4 2 5 1 6 3 7;直接上代码。

 public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    getNodeVal(list, root);
    return list;
}


public void getNodeVal(List<Integer> list, TreeNode root){
    if (null == root){
        return;
    }
    //前序遍历先添加 左->根->右 ,所以先添加左孩子的值
    getNodeVal(list, root.left);
    list.add(root.val);
    getNodeVal(list, root.right);
}  
  • 后序遍历

按照 左孩子-> 右孩子 -> 根节点 的方式遍历,每次先遍历左孩子,遍历结果为 4 5 2 6 7 3 1;直接上代码。

 public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    getNodeVal(list, root);
    return list;
}


public void getNodeVal(List<Integer> list, TreeNode root){
    if (null == root){
        return;
    }
    //前序遍历先添加 左->右->根 ,所以先添加左孩子的值
    getNodeVal(list, root.left);
    getNodeVal(list, root.right);
    list.add(root.val);
}  

  • 层级遍历

层次遍历就是按照每一层从左向右的方式进行遍历,每次先遍历左孩子,遍历结果为 1 2 3 4 5 6 7;

 public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> listResult = new ArrayList<>();
    if (null == root) {
        return listResult;
    }
    //声明一个队列
    Queue<TreeNode> treeNodeQueue = new LinkedList<>();
    //将头节点放入队列,此处用offer
    //offer,add 区别:
    //一些队列有大小限制,因此如果想在一个满的队列中加入一个新项,
    //多出的项就会被拒绝。这时新的 offer 方法就可以起作用了。
    //它不是对调用 add() 方法抛出一个 unchecked 异常,
    //而只是得到由 offer() 返回的false。
    treeNodeQueue.offer(root);
    //while每次循环都是操作一个层级的节点。 
    while (!treeNodeQueue.isEmpty()) {
        //获取队列的长度
        int size = treeNodeQueue.size();
        List<Integer> list = new ArrayList<>(size);
        //此处注意,只操作删除每个层级的节点,所以是1->size
        for (int i = 1; i <= size; ++i) {
            //poll,remove 区别:
            // remove()和 poll ()方法都是从队列中删除第一个元素。
            // remove()的行为与  Collection  接口的版本相似,但是
            // 新的poll()方法在用空集合调用时不是抛出异常,只是返回         
            // null。因此新的方法更适合容易出现异常条件的情况。
            TreeNode temp = treeNodeQueue.poll();
            if (temp == null) {
                break;
            }
            //添加当前层级节点值
            list.add(temp.val);
            //将当前节点加入队列中。
            if (temp.left != null) {
                treeNodeQueue.offer(temp.left);
            }
            if (temp.right != null) {
                treeNodeQueue.offer(temp.right);
            }
        }
        listResult.add(list);
    }
    return listResult;
}  

以上就是4种基本的遍历方式,看到这里大家是不是发现,所谓的就是前中后指的是根结点的位置,层级遍历这种思路也可以应用在查询二叉树的深度。

更多精彩可搜索gz号【程序猿日常笔记】

文章来源:智云一二三科技

文章标题:二叉树的遍历(左中右及层级)

文章地址:https://www.zhihuclub.com/197790.shtml

关于作者: 智云科技

热门文章

发表回复

您的电子邮箱地址不会被公开。

网站地图