Binary Tree Zigzag Level Order Traversal Algorithms using DFS an

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

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) —

推荐阅读：
数学题相遇时货车行了240km　 数学题:河边放养着一群鸭子　 还有10块钱哪儿去了　 数学题:实验小学五(1)班、五(2)班共有89人　 数学题:两个牧童放羊　 数学题:山路有多长　 数学题:七个裁判员给一名体操运动员评分　 在大学三下乡的反思　 开心作文650字　 残缺的美丽更完美　
评论列表
添加评论