面试题32 - III. 从上到下打印二叉树 III

题目描述：

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

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

返回其层次遍历结果：

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

提示：

节点总数 <= 1000

思路：

1、初始化一个存储当前层节点的tempLayerNode，一个存储下一层节点的nextLayerNode；
2、初始化一个存储当前层节点值的layerNum。
3、遍历当前层的所有节点tempLayerNode，如果是偶数层，则从右节点向左节点开始遍历，将当前节点的值添加到layerNum中，并分别将右左子节点添加到nextLayerNode中；如果是奇数层，则从左向右开始遍历，将当前节点的值添加到layerNum中，并分别将左右子节点添加到nextLayerNode中；当前层遍历结束后，将nextLayerNode中的节点放到tempLayerNode中，继续遍历。知道nextLayerNode中没有数据，也就是没有下层了。
4.返回结果。

Java解法（ArrayList）：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null)
        {
            return new ArrayList();
        }
        List<TreeNode> tempLayerNode =  new ArrayList<>();
        tempLayerNode.add(root);
        List<Integer> layerNum = new ArrayList<>();
        layerNum.add(root.val);
        ans.add(layerNum);
        int layer = 2;
        while(true)
        {
            List<TreeNode> nextLayerNode = new ArrayList();
            layerNum = new ArrayList();
            for(int i = tempLayerNode.size() - 1; i >= 0; i--) 
            {
                TreeNode curNode = tempLayerNode.get(i);
                
                if(layer % 2 == 0)
                {
                    if(curNode.right != null)
                    {
                        nextLayerNode.add(curNode.right);
                        layerNum.add(curNode.right.val);
                    }
                    if(curNode.left != null)
                    {
                        nextLayerNode.add(curNode.left);
                        layerNum.add(curNode.left.val);
                    }
                }else{
                    if(curNode.left != null)
                    {
                        nextLayerNode.add(curNode.left);
                        layerNum.add(curNode.left.val);
                    }
                    if(curNode.right != null)
                    {
                        nextLayerNode.add(curNode.right);
                        layerNum.add(curNode.right.val);
                    }
                }
            }
            layer++;
            if(layerNum.size() == 0) break;
            tempLayerNode = nextLayerNode;
            ans.add(layerNum);
        }
        return ans;     
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

最后编辑于：2020.03.01 12:15:14