1. 首页
  2. Leetcode经典148题

leetcode-103-Binary-Tree-Zigzag-Level-Order-Traversal

题目描述(中等难度)

leetcode-103-Binary-Tree-Zigzag-Level-Order-Traversal

“>102 题 吧,直接在 102 题的基础上进行修改即可。从左到右和从右到左交替,所以我们只需要判断当前的 level,层数从 0 开始的话,偶数就把元素添加到当前层的末尾,奇数的话,每次把新元素添加到头部,这样就实现了从右到左的遍历。

解法一 DFS

判断 level 是偶数还是奇数即可。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    DFS(root, 0, ans);
    return ans;
}

private void DFS(TreeNode root, int level, List<List<Integer>> ans) {
    if (root == null) {
        return;
    }
    if (ans.size() <= level) {
        ans.add(new ArrayList<>());
    }
    if ((level % 2) == 0) {
        ans.get(level).add(root.val); //添加到末尾
    } else {
        ans.get(level).add(0, root.val); //添加到头部
    }

    DFS(root.left, level + 1, ans);
    DFS(root.right, level + 1, ans);
}

解法二 BFS 队列

如果是顺序刷题,前边的 97 题 98 题101 题,都用到了 BFS ,应该很熟悉了。

之前我们用一个 while 循环,不停的从队列中拿一个节点,并且在循环中将当前取出来的节点的左孩子和右孩子也加入到队列中。

相比于这道题,我们要解决的问题是,怎么知道当前节点的 level

第一种方案

定义一个新的 class,class 里边两个成员 node 和 level,将我们新定义的 class 每次加入到队列中。或者用一个新的队列和之前的节点队列同步入队出队,新的队列存储 level。

下边的代码实现后一种,并且对 level 进行判断。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> treeNode = new LinkedList<>();
    Queue<Integer> nodeLevel = new LinkedList<>();
    treeNode.offer(root);
    int level = 0;
    nodeLevel.offer(level);
    while (!treeNode.isEmpty()) {
        TreeNode curNode = treeNode.poll();
        int curLevel = nodeLevel.poll();
        if (curNode != null) {
            if (ans.size() <= curLevel) {
                ans.add(new ArrayList<>());
            }
            if ((curLevel % 2) == 0) {
                ans.get(curLevel).add(curNode.val);
            } else {
                ans.get(curLevel).add(0, curNode.val);
            }
            level = curLevel + 1;
            treeNode.offer(curNode.left);
            nodeLevel.offer(level);
            treeNode.offer(curNode.right);
            nodeLevel.offer(level);
        }
    }
    return ans;
}

第二种方案

public List<List<Integer>> zigzagLevelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); List<List<Integer>> ans = new LinkedList<List<Integer>>(); if (root == null) return ans; queue.offer(root); while (!queue.isEmpty()) { int levelNum = queue.size(); // 当前层元素的个数 List<Integer> subList = new LinkedList<Integer>(); int level = 0; for (int i = 0; i < levelNum; i++) { TreeNode curNode = queue.poll(); if (curNode != null) { if ((level % 2) == 0) { subList.add(curNode.val); } else { subList.add(0, curNode.val); } queue.offer(curNode.left); queue.offer(curNode.right); } } //因为上边 queue.offer(curNode.left) 没有判断是否是 null //所以要判断当前是否有元素 if (subList.size() > 0) { ans.add(subList); } level++; } return ans; }

除了增加 level 变量外,我们还可以增加一个 boolean 变量来区别当前从左还是从右。此外 “>这里 看到一个有趣的想法,分享一下。

我们直接用两个栈(或者队列)轮换着添加元素,一个栈从左到右添加元素,一个栈从右到左添加元素。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    TreeNode c=root;
    List<List<Integer>> ans =new ArrayList<List<Integer>>();
    if(c==null) return ans;
    Stack<TreeNode> s1=new Stack<TreeNode>();
    Stack<TreeNode> s2=new Stack<TreeNode>();
    s1.push(root);
    while(!s1.isEmpty()||!s2.isEmpty())
    {
        List<Integer> tmp=new ArrayList<Integer>();
        while(!s1.isEmpty())
        {
            c=s1.pop();
            tmp.add(c.val);
            if(c.left!=null) s2.push(c.left);
            if(c.right!=null) s2.push(c.right);
        }
        ans.add(tmp);
        tmp=new ArrayList<Integer>();
        while(!s2.isEmpty())
        {
            c=s2.pop();
            tmp.add(c.val);
            if(c.right!=null)s1.push(c.right);
            if(c.left!=null)s1.push(c.left);
        }
        if(!tmp.isEmpty()) ans.add(tmp);
    }
    return ans;
}

这道题和

阅读全文

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
  4. JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

    本文著作权归作者所有,如若转载,请注明出处

    转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

    标题:leetcode-103-Binary-Tree-Zigzag-Level-Order-Traversal

    链接:https://www.javajike.com/article/3240.html

« leetcode-102-Binary-Tree-Level-Order-Traversal
leetcode-104-Maximum-Depth-of-Binary-Tree»

相关推荐

QR code