本文共 1334 字,大约阅读时间需要 4 分钟。
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]]
解题思路:
层次遍历二叉树,用一个标记来确定该层需要从左到右还是从右到左。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { List
> res; boolean flag; public List
> zigzagLevelOrder(TreeNode root) { flag = true; res = new ArrayList
>(); List node = new ArrayList (); if(root != null && node.add(root)) levelValue(node); return res; } public void levelValue(List node){ TreeNode tn; TreeNode td; List value = new ArrayList (); List temp = new ArrayList (); if(node.size() == 0) return ; for(int i = 0; i < node.size(); i++){ tn = node.get(i); value.add(tn.val); td = node.get(node.size()-1-i); if(flag){ if(td.right != null && temp.add(td.right)); if(td.left != null && temp.add(td.left)); } else{ if(td.left != null && temp.add(td.left)); if(td.right != null && temp.add(td.right)); } } flag = !flag; res.add(value); levelValue(temp); }}
转载地址:http://ativi.baihongyu.com/