Binary Tree Zigzag Level Order Traversal Algorithms using DFS an

  • 时间：2020-09-18 17:39:21
  • 分类：网络文摘
  • 阅读：143 次

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,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

1
2
3
4
5

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

We can accomplish the task by using DFS or BFS algorithms where in DFS, we require tracking the levels (passing the depth value down the tree) and in BFS, we inherently expand the tree level by level.

Depth First Search (Recursion) Algorithm to Zigzag Level Order Traval the Binary Tree

Let’s pass the depth of the node when doing recursive depth first search. And we can use the depth to output the order to the corresponding index of the result vector. By checking if the depth is odd or even, we know that particular level should be in reverse order or not.

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

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        dfs(root, 0);
        return res;
    }
private:
    vector<vector<int>> res;
    
    void dfs(TreeNode* root, int depth) {
        if (root == nullptr) return;
        if (res.size() <= depth) {
            res.push_back({});
        }
        if (depth % 2 == 0) {
            res[depth].push_back(root->val);
        } else {
            res[depth].insert(begin(res[depth]), root->val);
        }        
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);        
    }
};
/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        dfs(root, 0);
        return res;
    }
private:
    vector<vector<int>> res;
    
    void dfs(TreeNode* root, int depth) {
        if (root == nullptr) return;
        if (res.size() <= depth) {
            res.push_back({});
        }
        if (depth % 2 == 0) {
            res[depth].push_back(root->val);
        } else {
            res[depth].insert(begin(res[depth]), root->val);
        }        
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);        
    }
};

We can use the std::vector().push_back to append an element to the vector or std::vector.insert() together with the begin() vector to insert an element to the front of a vector.

The time complexity for DFS is O(N) where each node is visited exactly once. The space complexity is O(N) where N is the number of the nodes in the tree (considering the tree can be just a linked list hence Height = N for recursion). Here, we don’t consider the output vector, which clearly requires O(N^2) space.

How to do Zigzag Level Order Traversal for a Binary Tree using Breadth First Search Algorithm?

The iterative approach could be using the BFS (breadth first search) where we pop all elements from the queue (which belong to the same level), and push their children (which will be of the same level as well).

The level is recorded while we expand the tree using BFS level by level. We can reverse the level vector using std::reverse()

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
38

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        if (root == nullptr) return res;
        Q.push(root);        
        int level = 0;
        while (!Q.empty()) {
            int num = Q.size();
            vector<int> r;
            for (int i = 0; i < num; ++ i) {
                auto p = Q.front();
                Q.pop();
                if (p->left) Q.push(p->left);
                if (p->right) Q.push(p->right);
                r.push_back(p->val);
            }                
            if (level % 2 == 1) {
                std::reverse(begin(r), end(r));
            }
            if (!r.empty()) {
                res.push_back(r);
            }
            level ++;
        }
        return res;
    }
};
/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        if (root == nullptr) return res;
        Q.push(root);        
        int level = 0;
        while (!Q.empty()) {
            int num = Q.size();
            vector<int> r;
            for (int i = 0; i < num; ++ i) {
                auto p = Q.front();
                Q.pop();
                if (p->left) Q.push(p->left);
                if (p->right) Q.push(p->right);
                r.push_back(p->val);
            }                
            if (level % 2 == 1) {
                std::reverse(begin(r), end(r));
            }
            if (!r.empty()) {
                res.push_back(r);
            }
            level ++;
        }
        return res;
    }
};

Alternatively, we can decide to push to the back or insert to the front of the level vector depending on the oddness of the level – This approach/implementation is slightly faster.

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
38
39

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        if (root == nullptr) return res;
        Q.push(root);        
        int level = 0;
        while (!Q.empty()) {
            int num = Q.size();
            vector<int> r;
            for (int i = 0; i < num; ++ i) {
                auto p = Q.front();
                Q.pop();
                if (p->left) Q.push(p->left);
                if (p->right) Q.push(p->right);
                if (level % 2 == 0) {
                    r.push_back(p->val);
                } else {
                    r.insert(begin(r), p->val);
                }
            }                
            if (!r.empty()) {
                res.push_back(r);
            }
            level ++;
        }
        return res;
    }
};
/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        if (root == nullptr) return res;
        Q.push(root);        
        int level = 0;
        while (!Q.empty()) {
            int num = Q.size();
            vector<int> r;
            for (int i = 0; i < num; ++ i) {
                auto p = Q.front();
                Q.pop();
                if (p->left) Q.push(p->left);
                if (p->right) Q.push(p->right);
                if (level % 2 == 0) {
                    r.push_back(p->val);
                } else {
                    r.insert(begin(r), p->val);
                }
            }                
            if (!r.empty()) {
                res.push_back(r);
            }
            level ++;
        }
        return res;
    }
};

The time complexity for BFS is also O(N). Below is the Python Implemetation of the same algorithm using BFS.

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if root is None:
            return res
        q = [root]
        level = 0
        while len(q) > 0:
            cur = []
            level += 1            
            sz = len(q)
            for i in range(sz):
                cur.append(q[i].val)
                if q[i].left:
                    q.append(q[i].left)
                if q[i].right:
                    q.append(q[i].right)                
            for i in range(sz):
                q.pop(0)
            if level % 2 == 0:
                cur.reverse()
            res.append(cur)
        return res
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if root is None:
            return res
        q = [root]
        level = 0
        while len(q) > 0:
            cur = []
            level += 1            
            sz = len(q)
            for i in range(sz):
                cur.append(q[i].val)
                if q[i].left:
                    q.append(q[i].left)
                if q[i].right:
                    q.append(q[i].right)                
            for i in range(sz):
                q.pop(0)
            if level % 2 == 0:
                cur.reverse()
            res.append(cur)
        return res

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
百家讲坛系列节目《于丹〈论语〉心得》MP3蓝奏云下载　 吴许越成原文及翻译　 诗词名句鉴赏：我所思兮在太山，欲往从之梁父艰。　 诗词名句鉴赏：大风起兮云飞扬，威加海内兮归故乡。　 百家讲坛系列节目《于丹〈庄子〉心得》MP3蓝奏云下载　 诗词名句鉴赏：男儿爱后妇，女子重前夫。　 诗词名句鉴赏：居异土国兮心内伤，愿为黄鹄兮归故乡。　 子革对灵王原文及翻译　 写人作文乐趣作文900字　 关于都江堰的写景作文　
评论列表
添加评论