leetcode-103-Binary-Tree-Zigzag-Level-Order-Traversal

发表于   |  

描述

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},

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

分析

和Binary Tree Level Order Traversal以及Binary Tree Level Order Traversal II类似，不过这里的走法是「蛇形的」，用一个bool变量进行记录即可。时间复杂度是O(n), 空间复杂度是O(n)。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> result;
    
    void leveltravel(TreeNode* root, int level, bool left2right) {
        if(root == NULL) {
            return ;
        }
        if(level == result.size()) {
            vector<int> v;
            result.push_back(v);
        }
        
        if(left2right) {
            result[level].push_back(root->val);
        }else {
            result[level].insert(result[level].begin(), root->val);
        }
        
        leveltravel(root->left, level+1, !left2right);
        leveltravel(root->right, level+1, !left2right);
    }
    
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        leveltravel(root, 0, true);
        return result;
    }
};

解决方案2(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def zigzagLevelOrder(self, root):
        def dfs(root, level, left2right):
            if root is None:
                return ;
            
            if level == len(result):
                result.append([])
            if left2right is True:
                result[level].append(root.val)
            else:
                result[level].insert(0, root.val)
            if root.left:
                dfs(root.left, level+1, not left2right)
            if root.right:
                dfs(root.right, level+1, not left2right)
        result = []
        dfs(root, 0, True)
        return result

解决方案3（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    queue := []*TreeNode{root}
    var result [][]int
    
    for level := 0; len(queue) > 0; level++ {
        now := []int{}
        nowQueue := queue
        queue = nil
        for _, node := range nowQueue {
            now = append(now, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        if level % 2 == 1 {
            for i, nowLens := 0, len(now); i < nowLens/2; i++ {
                now[i], now[nowLens-1-i] = now[nowLens-1-i], now[i]
            }
        }
        result = append(result, now)
    }
    return result
}

相关问题

题目来源