ITKeyword,专注技术干货聚合推荐

注册 | 登录

【LeetCode-面试算法经典-Java实现】【103-Binary Tree Zigzag Level Order Traversal(二叉树分层Z字形遍历)】

DERRANTCM 分享于 2015-08-08

推荐:【LeetCode-面试算法经典-Java实现】【107-Binary Tree Level Order Traversal II(二叉树层序遍历II)】

【107-Binary Tree Level Order Traversal II(二叉树层序遍历II)】 【LeetCode-面试算法经典-Java实现】【所有题目目录索引】 原题   Given a binary tree,

2020腾讯云共同战“疫”,助力复工(优惠前所未有!4核8G,5M带宽 1684元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1053

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

【103-Binary Tree Zigzag Level Order Traversal(二叉树分层Z字形遍历)】

【LeetCode-面试算法经典-Java实现】【所有题目目录索引】

原题

  Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
  For example:
  Given binary tree {3,9,20,#,#,15,7},

    3
   / \   9  20
    /  \    15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

题目大意

  给定一棵二叉树,从顶向下,进行Z字形分层遍历,即:如果本层是从左向右的,下层就是从右向左。

推荐:【LeetCode-面试算法经典-Java实现】【144-Binary Tree Preorder Traversal(二叉树非递归前序遍历)】

【144-Binary Tree Preorder Traversal(二叉树非递归前序遍历)】 【LeetCode-面试算法经典-Java实现】【所有题目目录索引】 原题   Given a binary tree, re

解题思路

  二叉树分层遍历进行改进,使用两个栈来进行。

代码实现

树结点类

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

算法实现类

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/** * Author: 王俊超 * Date: 2015-06-23 * Time: 13:24 * Declaration: All Rights Reserved !!! */
public class Solution {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();

        if (root == null) {
            return result;
        }
        // 遍历标志,0表示从左到右,1表示从右到左
        int flag = 0;
        TreeNode node;
        // 记录每一层的元素
        List<Integer> lay = new LinkedList<>();
        // 双向队列,当作栈来使用,记录当前层待处理结点
        Deque<TreeNode> stack = new LinkedList<>();
        // 记录下一层待处理结点
        Deque<TreeNode> nextStack = new LinkedList<>();

        stack.add(root);

        while (!stack.isEmpty()) {
            // 删除栈顶元素
            node = stack.removeLast();

            // 结果入队
            lay.add(node.val);

            // 如果当前是从左到右遍历,按左子树右子树的顺序添加
            if (flag == 0) {
                if (node.left != null) {
                    nextStack.addLast(node.left);
                }

                if (node.right != null) {
                    nextStack.addLast(node.right);
                }
            }
            // 如果当前是从右到左遍历,按右子树左子树的顺序添加
            else {
                if (node.right != null) {
                    nextStack.addLast(node.right);
                }

                if (node.left != null) {
                    nextStack.addLast(node.left);
                }
            }

            // 当前层已经处理完了
            if (stack.isEmpty()) {
                Deque<TreeNode> temp = nextStack;
                nextStack = stack;
                stack = temp;

                // 标记下一层处理的方向
                flag = 1 - flag;
                // 保存本层结果
                result.add(lay);
                // 创建新的链表处理下一层的结果
                lay = new LinkedList<>();
            }
        }

        return result;
    }
}

评测结果

  点击图片,鼠标不释放,拖动一段位置,释放后在新的窗口中查看完整图片。

这里写图片描述

特别说明

欢迎转载,转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47354341

推荐:【LeetCode-面试算法经典-Java实现】【094-Binary Tree Inorder Traversal(二叉树中序遍历)】

【094-Binary Tree Inorder Traversal(二叉树中序遍历)】 【LeetCode-面试算法经典-Java实现】【所有题目目录索引】 原题   Given a binary tree, return th

【103-Binary Tree Zigzag Level Order Traversal(二叉树分层Z字形遍历)】 【LeetCode-面试算法经典-Java实现】【所有题目目录索引】 原题   Given a binary tree, return the zigzag level

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。