leetcode103-二叉树的锯齿形层次遍历

原题

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

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

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下:

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

解法

思想

用两个栈来交替存储某一层和下一层的节点:

读取第一个栈的时候,从左向右的读取节点,将它们的子节点从左向右入第二个栈,能使读取第二个栈的时候是以从右向左的顺序出栈的。

读取第二个栈的时候,从右向左的读取节点,将它们的子节点从右向左入第一个栈,能使读取第一个栈的时候是以从左向右的顺序出栈的。

这样交替使用两个栈,可以实现两层之间的顺序反转。

代码

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Stack<TreeNode> first = new Stack<>();
        Stack<TreeNode> second = new Stack<>();
        List<Integer> cur;
        if(root == null) return ans;
        first.push(root);
        while(!first.isEmpty()||!second.isEmpty()){
            //当前层的节点按从左向右的顺序依次出栈,子节点按从左向右的顺序入second栈,实现顺序逆转
            cur = new ArrayList<>();
            while(!first.isEmpty()){
                TreeNode node = first.pop();
                cur.add(node.val);
                if(node.left!=null) second.push(node.left);
                if(node.right!=null) second.push(node.right);
            }
            ans.add(cur);
            //下一层的节点按从右向左的顺序依次出栈,子节点按从右向左的顺序入first栈,实现顺序逆转
            if(second.isEmpty()) break;
            cur = new ArrayList<>();
            while(!second.isEmpty()){
                TreeNode node = second.pop();
                cur.add(node.val);
                if(node.right!=null) first.push(node.right);
                if(node.left!=null) first.push(node.left);
            }
            ans.add(cur);
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode103-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e9%94%af%e9%bd%bf%e5%bd%a2%e5%b1%82%e6%ac%a1%e9%81%8d%e5%8e%86/