vim复制 log4j macos generics redux dll bitmap mui 相亲网站源码 android实战项目 jq遍历 office2016修复 matlab对数函数 idea整理代码 matlab不等于怎么表示 SketchUp python逻辑运算符 python基础代码 java9 java时间 javasocket通信 java线程中断 java生成当前时间 java重命名 linux系统简介 路由器辐射大吗 图片链接生成器 字幕制作软件哪个好 js转int unix系统下载 infopath下载 编程语言实现模式 刷新页面 js小数点保留2位 pr蒙版 xapk安装器 ps3d字体 求字符串长度 linux系统下载 文件分割
当前位置: 首页 > 学习教程  > 编程语言

二叉树的锯齿形层次遍历(Java)

2020/12/5 11:01:16 文章标签:

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ …

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

示例:
给定二叉树 [3,9,20,null,null,15,7],

             3
          /    \
       9        20
              /       \
         15           7

返回锯齿形层次遍历如下:
[
  [3],
  [20,9],
  [15,7]
]


package com.loo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class ZigzagOrder {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left1 = new TreeNode(2);
        TreeNode right1 = new TreeNode(3);
        TreeNode left2 = new TreeNode(4);
        TreeNode left3 = new TreeNode(5);
//        TreeNode right2 = new TreeNode(6);
        TreeNode right3 = new TreeNode(7);
        root.left = left1;
        root.right = right1;
        left1.left = left2;
        left1.right = left3;
        right1.right = right3;
        List<List<Integer>> list = getZigzagOrder1(root);
        for (List<Integer> l : list) {
            System.out.println(Arrays.toString(l.toArray()));
        }
        System.out.println("+++++++++++++++++++++++++++++++++++");
        TreeNode root2 = new TreeNode(3);
        TreeNode left21 = new TreeNode(9);
        TreeNode right21 = new TreeNode(20);
        TreeNode right22 = new TreeNode(15);
        TreeNode right23 = new TreeNode(7);
        root2.left = left21;
        root2.right = right21;
        right21.left = right22;
        right21.right = right23;
        List<List<Integer>> list2 = getZigzagOrder2(root2);
        for (List<Integer> l : list2) {
            System.out.println(Arrays.toString(l.toArray()));
        }
    }

    // BFS(广度优先遍历),将要访问的节点添加到队列中,使用分隔符(例如:空节点)把不同层的节点分隔开。分隔符表示一层结束和新一层开始。
    // 如果需要 FIFO(先进先出)的顺序,则将新元素添加到队列尾部,后插入的元素就可以排在后面。如果需要 FILO(先进后出)的顺序,则将新元素添加到队列首部,后插入的元素就可以排在前面。
    public static List<List<Integer>> getZigzagOrder1(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.addLast(root);
        queue.addLast(null);
        LinkedList<Integer> level = new LinkedList<Integer>();
        boolean isOrderLeft = true;
        while (queue.size()>0) {
            TreeNode currNode = queue.pollFirst();
            if (currNode!=null) {
                if (isOrderLeft) {
                    level.addLast(currNode.value);
                } else {
                    level.addFirst(currNode.value);
                }
                if (currNode.left!=null) {
                    queue.addLast(currNode.left);
                }
                if (currNode.right!=null) {
                    queue.addLast(currNode.right);
                }
            } else {
                result.add(level);
                level = new LinkedList<Integer>();
                if (queue.size()>0) {
                    queue.addLast(null);
                }
                isOrderLeft = !isOrderLeft;
            }
        }
        return result;
    }

    // DFS (深度优先遍历)
    // 如果是第一次访问该层的节点,即该层的双端队列不存在。那么创建一个双端队列,并添加该节点到队列中。
    // 如果当前层的双端队列已存在,根据顺序,将当前节点插入队列头部或尾部。
    // 最后为每个节点调用该递归方法。
    public static List<List<Integer>> getZigzagOrder2(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        dfs(root , 0 , results);
        return results;
    }
    
    public static void dfs(TreeNode node , int level , List<List<Integer>> list) {
        if (level >= list.size()) {
            LinkedList<Integer> newLevelList = new LinkedList<Integer>();
            newLevelList.add(node.value);
            list.add(newLevelList);
        } else {
            if ((level & 1) == 0) {
                list.get(level).add(node.value);
            } else {
                list.get(level).add(0, node.value);
            }
        }
        if (node.left!=null) {
            dfs(node.left , level + 1 , list);
        }
        if (node.right!=null) {
            dfs(node.right , level + 1 , list);
        }
    }
    
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode(int v) {
            value = v;
        }
    }

}

 


本文链接: http://www.dtmao.cc/news_show_450378.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?