[leetcode]103. Binary Tree Zigzag Level Order Traversal二叉树Z字形层序遍历

相对于102题，稍微改变下方法就行

迭代方法：

在102题的基础上，加上一个变量来判断是不是需要反转

反转的话，当前list在for循环结束后用collection的反转方法就可以实现反转

递归方法：

由于有层数，所以用层数%2判断是不是需要反转

反转的话就元素都添加到最前边，一层添加完后就是反的

下边是递归方法

List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        /*

        递归方法是判断当前层是否需要反转

        反转层添加方法：元素总是添加到第一个，这样就相当于反转了

        非反转层正常添加

         */

        helper(root,0);

        return res;

    }

    public void helper(TreeNode root,int c)

    {

        if (root==null)

            return;

        if (res.size()==c)

            res.add(new ArrayList<>());

        List<Integer> cur = res.get(c);

        if (c%2==0) cur.add(root.val);

        else cur.add(0,root.val);

        if (root.left!=null)

            helper(root.left,c+1);

        if (root.right!=null)

            helper(root.right,c+1);

    }

这个题一开始没做出来是因为：

觉得反转的情况应该反向添加（递归）节点，但是发现不行，因为如果反向添加（递归）节点，那么下个节点就会全部自动反向

应该是反向添加数值，节点的遍历顺序不能动

巴特西

[leetcode]103. Binary Tree Zigzag Level Order Traversal二叉树Z字形层序遍历

最新文章

热门文章