Binary Tree Zigzag Level Order Traversal-K6K4.com

原题： https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

题意： 给定一个二叉树，实现它的之字形层序遍历。

约定：（1）从左到右，然后下一层再从右到左，如此交替遍历。

例子：

给定二叉树：[3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
返回它的之字形层序遍历为：
[
  [3],
  [20,9],
  [15,7]
]

标签： zigzag、之字形、层序、traversal、binary、面试

猜你感兴趣的圈子：

LeetCode交流圈

Bingo

2017-08-12 10:52:08 1楼#1层

C++：

/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
  
    vector<vector<int> >zigzagLevelOrder(TreeNode *root){  
        vector<vector<int> > result;  
        queue<NodeWithLevel> q;  
        q.push(NodeWithLevel(root, 0));  
        while (!q.empty())  
        {  
            NodeWithLevel cur = q.front(); q.pop();  
            TreeNode *p = cur.p;  
            if(p){  
                if(result.size() <= cur.level){  
                    vector<int> tem;  
                    tem.push_back(p->val);  
                    result.push_back(tem);  
      
                }else{  
                    result[cur.level].push_back(p->val);  
                }  
                NodeWithLevel left(p->left, cur.level + 1);  
                NodeWithLevel right(p->right, cur.level + 1);  
                q.push(left);  
                q.push(right);  
            }  
        }  
        for(int i = 1; i < result.size(); i += 2) reverse(result[i].begin(), result[i].end());  
        return result;  
    }  
  
private:  
    struct NodeWithLevel{  
        TreeNode *p;  
        int level;  
        NodeWithLevel(TreeNode *pp, int l):p(pp), level(l){}  
    };  
      
};

Bingo

2017-08-12 10:54:58 2楼#1层

Java解法一：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int i = queue.size(); // 记录每层的结点个数
        boolean flag = false;
        TreeNode tempNode = null;
        List<Integer> singleLevel = new ArrayList<>();
        while (!queue.isEmpty()) {
            if (i == 0) {// 一层记录结束
                //
                if (flag) {
                    Collections.reverse(singleLevel);
                }
                result.add(singleLevel);
                //
                flag = !flag;

                i = queue.size();
                singleLevel = new ArrayList<>();
            }
            tempNode = queue.poll();
            singleLevel.add(tempNode.val);

            --i;

            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }
            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }

        }
        if (flag) {
            Collections.reverse(singleLevel);
        }
        result.add(singleLevel);

        return result;
    }
    public List<List<Integer>> zigzagLevelOrder5(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int i = queue.size(); // 记录每层的结点个数
        boolean flag = true;
        TreeNode tempNode = null;
        LinkedList<Integer> singleLevel = new LinkedList<>();
        while (!queue.isEmpty()) {
            if (i == 0) {// 一层记录结束
                //
                result.add(singleLevel);
                //
                i = queue.size();
                singleLevel = new LinkedList<>();
                flag = !flag;
            }
            tempNode = queue.poll();
            if (flag) {
                singleLevel.add(tempNode.val);
            } else {
                singleLevel.addFirst(tempNode.val);
            }

            --i;

            if (tempNode.left != null) {
                queue.offer(tempNode.left);
            }
            if (tempNode.right != null) {
                queue.offer(tempNode.right);
            }

        }

        result.add(singleLevel);
        return result;
    }
}

Bingo

2017-08-12 10:56:54 3楼#1层

Java解法二：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        // levelRecursion(root, result, 0, false);
        levelRecursion2(root, result, 0);

        return result;
    }
    /**
     * 递归方法
     */
    private void levelRecursion(TreeNode node, List<List<Integer>> result,
            int level, boolean flag) {
        if (node == null) {
            return;
        }
        if (result.size() < level + 1) {// 说明还需要添加一行
            result.add(new LinkedList<Integer>());
        }
        if (flag) {
            ((LinkedList<Integer>) result.get(level)).addFirst(node.val);
        } else {
            result.get(level).add(node.val);
        }

        levelRecursion(node.left, result, level + 1, !flag);
        levelRecursion(node.right, result, level + 1, !flag);
    }

    /**
     * 可以直接通过level层级判断是否需要addFirst，不必要再添加额外的标识
     * 
     * @param node
     * @param result
     * @param level
     */
    private void levelRecursion2(TreeNode node, List<List<Integer>> result,
            int level) {
        if (node == null) {
            return;
        }
        if (result.size() < level + 1) {// 说明还需要添加一行
            result.add(new LinkedList<Integer>());
        }
        if (level % 2 != 0) {
            ((LinkedList<Integer>) result.get(level)).addFirst(node.val);
        } else {
            result.get(level).add(node.val);
        }

        levelRecursion2(node.left, result, level + 1);
        levelRecursion2(node.right, result, level + 1);
    }
}

Bingo

2017-08-12 10:57:58 4楼#1层

Java解法三：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (root == null) {
            return result;
        }

        Stack<TreeNode> forwardStack = new Stack<>();
        Stack<TreeNode> retrorseStack = new Stack<>();

        forwardStack.push(root);

        TreeNode tempNode = null;
        List<Integer> singleList = new ArrayList<>();
        while (!forwardStack.isEmpty() || !retrorseStack.isEmpty()) {
            while (!forwardStack.isEmpty()) {
                tempNode = forwardStack.pop();
                singleList.add(tempNode.val);
                if (tempNode.left != null) {
                    retrorseStack.push(tempNode.left);
                }
                if (tempNode.right != null) {
                    retrorseStack.push(tempNode.right);
                }
            }

            if (!singleList.isEmpty()) {
                result.add(singleList);
                singleList = new ArrayList<>();
            }

            while (!retrorseStack.isEmpty()) {
                tempNode = retrorseStack.pop();
                singleList.add(tempNode.val);
                if (tempNode.right != null) {
                    forwardStack.push(tempNode.right);
                }
                if (tempNode.left != null) {
                    forwardStack.push(tempNode.left);
                }
            }

            if (!singleList.isEmpty()) {
                result.add(singleList);
                singleList = new ArrayList<>();
            }
        }

        return result;
    }
}

取消

回复

推荐圈子

LeetCode交流圈