代码天涯路

103. 二叉树的锯齿形层次遍历(Binary Tree Zigzag Level Order Traversal)M

英文题目

  • 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:

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

中文题目

  • 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

  • 例如：

  •     3
   / \
  9  20
    /  \
   15   7

  • 给定二叉树 [3,9,20,null,null,15,7],

  • 返回锯齿形层次遍历如下：

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

BFS

  • 层次遍历稍微变一下即可

  • 时间复杂度O(n)，空间复杂度O(n)

    # python3: 时间 44 ms, 击败 51.11%; 内存 16.5 MB, 击败 11.44%
# 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: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res
        q = deque([root])
        level = 0
        while q:
            size = len(q)
            levelList = []
            for _ in range(size):
                node = q.popleft()
                levelList.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if level % 2 == 0:
                res.append(levelList)
            else:
                res.append(levelList[::-1])
            level += 1
        return res

    // c++: 时间 8 ms, 击败 16.94%; 内存 11.9 MB, 击败 43.45%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        int level = 0;
        while (!q.empty()) {
            int size = q.size();
            vector<int> levelList;
            for (int i = 0; i < size; ++i) {
                TreeNode * node = q.front();
                q.pop();
                levelList.push_back(node->val);
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            if (level % 2 == 0) {
                res.push_back(levelList);
            } else {
                reverse(levelList.begin(), levelList.end());
                res.push_back(levelList);
            }
            ++level;
        }
        return res;
    }
};

    // java: 时间 1 ms, 击败 72.90%; 内存 40.1 MB, 击败 88.90%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> levelList = new ArrayList<>();
            for (int i = 0; i < size; ++i) {
                TreeNode node = q.peek();
                q.poll();
                levelList.add(node.val);
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            if (level % 2 == 0) {
                res.add(levelList);
            } else {
                Collections.reverse(levelList);
                res.add(levelList);
            }
            ++level;
        }
        return res;
    }
}

    // go: 时间 0 ms, 击败 100%; 内存 2.32 MB, 击败 39.73%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }
    q := []*TreeNode{root}
    level := 0
    for len(q) > 0 {
        size := len(q)
        levelList := []int{}
        for i := 0; i < size; i++ {
            node := q[0]
            q = q[1:]
            levelList = append(levelList, node.Val)
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
        if level % 2 == 0 {
            res = append(res, levelList)
        } else {
            res = append(res, reverse(levelList))
        }
        level++
    }
    return res
}

func reverse(nums []int) []int {
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
    return nums
}

    // javascript: 时间 60 ms, 击败 86.89%; 内存 41.85 MB, 击败 43.02%
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    const res = [];
    if (!root) {
        return res;
    }
    const q = [root];
    let level = 0;
    while (q.length) {
        const size = q.length;
        const levelList = [];
        for (let i = 0; i < size; ++i) {
            const node = q.shift();
            levelList.push(node.val);
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
        if (level % 2 == 0) {
            res.push(levelList);
        } else {
            res.push(levelList.reverse());
        }
        ++level;
    }
    return res;
};

DFS

  • 本质即二叉树的先序遍历，只是在不同层插入数组的位置有区别

  • 时间复杂度O(n)，空间复杂度O(n)

    # python3: 时间 40 ms, 击败 72.81%; 内存 15.90 MB, 击败 59.50%
# 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: Optional[TreeNode]) -> List[List[int]]:
        self.res = []
        self.dfs(root, 0)
        return self.res
    
    # level是当前层次，root为第0层
    def dfs(self, root: Optional[TreeNode], level: int) -> None:
        if not root:
            return
        if len(self.res) <= level:
            self.res.append([])
        if level % 2 == 0:
            self.res[level].append(root.val)
        else:
            self.res[level].insert(0, root.val)
        self.dfs(root.left, level+1)
        self.dfs(root.right, level+1)

    // c++: 时间 4 ms, 击败 62.51%; 内存 12.10 MB, 击败 5.03%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        dfs(res, root, 0);
        return res;
    }

    void dfs(vector<vector<int>>& res, TreeNode* root, int level) {
        if (root == nullptr) {
            return;
        }
        if (res.size() <= level) {
            res.push_back(vector<int>());
        }
        if (level % 2 == 0) {
            res[level].push_back(root->val);
        } else {
            res[level].insert(res[level].begin(), root->val);
        }
        dfs(res, root->left, level+1);
        dfs(res, root->right, level+1);
    }
};

    // java: 时间 0 ms, 击败 100%; 内存 39.13 MB, 击败 86.66%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, root, 0);
        return res;
    }

    private void dfs(List<List<Integer>> res, TreeNode root, int level) {
        if (root == null) {
            return;
        }
        if (res.size() <= level) {
            res.add(new ArrayList<>());
        }
        if (level % 2 == 0) {
            res.get(level).add(root.val);
        } else {
            res.get(level).add(0, root.val);
        }
        dfs(res, root.left, level+1);
        dfs(res, root.right, level+1);
    }
}

    // go: 时间 0 ms, 击败 100%; 内存 2.70 MB, 击败 6.71%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    dfs(&res, root, 0)
    return res
}

func dfs(res *[][]int, root *TreeNode, level int) {
    if root == nil {
        return
    }
    if len(*res) <= level {
        *res = append(*res, []int{})
    }
    if level % 2 == 0 {
        (*res)[level] = append((*res)[level], root.Val)
    } else {
        (*res)[level] = append([]int{root.Val}, (*res)[level]...)
    }
    dfs(res, root.Left, level+1)
    dfs(res, root.Right, level+1)
}

    // javascript: 时间 56 ms, 击败 95.13%; 内存 41.88 MB, 击败 34.79%
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    const res = [];
    dfs(res, root, 0);
    return res;
};

const dfs = function(res, root, level) {
    if (root == null) {
        return;
    }
    if (res.length <= level) {
        res.push([]);
    }
    if (level % 2 == 0) {
        res[level].push(root.val);
    } else {
        res[level].unshift(root.val);
    }
    dfs(res, root.left, level+1);
    dfs(res, root.right, level+1);
}
Last Updated:
Contributors: Shiqi Lu