TechNomads

题目描述

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

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

    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层次遍历如下：

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

解法1-DFS

根据DFS遍历，奇数层按倒序插入。

Java代码如下：

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

    public void zLevelOrder(TreeNode node, List<List<Integer>> result, int level) {
        if (node == null) {
            return;
        }

	// 初始化数组
        if (result.size() == level) {
            result.add(new ArrayList<Integer>());
        }

        // 奇数
        if ((level & 1) == 1) {
            result.get(level).add(0, node.val);
        } else {
            result.get(level).add(node.val);
        }
	// 递归
        zLevelOrder(node.left, result, level + 1);
        zLevelOrder(node.right, result, level + 1);
    }

Go 代码如下：

var result [][] int

func zigzagLevelOrder(root *TreeNode) [][]int {
	result = [][]int{}
	zLevelOrder(root, 0)
	return result
}

func zLevelOrder(node *TreeNode, level int) {
	if node == nil {
		return
	}

	if len(result) == level {
		result = append(result, []int{})
	}

	if (level & 1) == 1 {
		result[level] = append([]int {node.Val}, result[level]...)
	} else {
		result[level] = append(result[level], node.Val)
	}
	zLevelOrder(node.Left, level + 1)
	zLevelOrder(node.Right, level + 1)
}

解法2-BFS

采用迭代的方式，通过队列来保存节点。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // List<List<Integer>> result = new ArrayList<>();
        // zLevelOrder(root, result, 0);
        // return result;

        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root != null){
            queue.add(root);
            int step = 0;
            while(queue.size() != 0){
                ArrayList<Integer> temp = new ArrayList<>();
                int size = queue.size();
                for(int i = 0;i < size;i++){
                    TreeNode cur = queue.poll();
                    temp.add(cur.val);
                    if(cur.left != null){
                        queue.add(cur.left);
                    }
                    if(cur.right != null){
                        queue.add(cur.right);
                    }
                }
                if(step % 2 == 1){ //右到左
                    Collections.reverse(temp);
                }
                res.add(temp);
                step++;
            }
        }

        return res;
    }