Binary Tree Zigzag Level Order Traversal Algorithms using DFS an

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

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

推荐阅读：
糖尿病患者常有这些饮食误区，朋友们注意啦！　 网络上流传甚广的垃圾食品方便面有毒、致癌的传闻是真的吗？　 经常吃核桃仁可以补脑是真的吗 一天吃多少核桃才健康　 甘蓝汁食疗方法对胃病患者非常有益 疗效甚至超过单纯药物　 面部出现这些变化则是男人肾虚要进行饮食调理　 酱油吃多了会导致皮肤变黑吗？别再被忽悠啦！　 健康饮食：人们都说吃了“隔夜菜”致癌，这是真的吗？　 豆腐味美又养生，做一道家常菜让你胃口大开　 女性在特殊时期饮食需要注意，不能吃这些食物　 此菜肴脆嫩爽口肉香浓郁且色香味俱全，为冬季百吃不厌的佳肴　
评论列表
添加评论