原题

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

例如:
给定二叉树: [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/

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

原题

解法

思想

代码

相关推荐

发表回复