• 关键字:树,宽度优先搜索
  • 难度:易
  • 题目大意:通过遍历,将一个颗二叉树每一层的节点找出来。并记录它们分别属于哪一层。

题目描述

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:

Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

解法

虽然本题题目的TAG给定的为宽度优先算法,但实际上用深度优先算法同样能解决。

我们在dfs的过程中直接记录一下当前递归到第几层,就可能找到当前节点对应着哪一行数组。

在同一层中,所有节点按照从左到右的顺序排列,为了实现这一点,我们需要让遍历节点的顺序也同样满足先到左边子树的节点,再到右边子树的节点。

所以我们DFS的过程可以总结为:

  • 将当前层节点的值加入到对应的数组中

  • 先递归处理左子树,再处理右子树

由于我们实现并不知道整个子树的层数,所以我们还需要根据当前的层数去动态增加我们答案的数组数量。

当然这一步的实现也很简单,只要比较一下当前层数和答案数组数量之间的关系就可以。

根据上面的结论,也就得到了我们的代码。具体实现可以参考下面的代码。

参考代码

class Solution {
    vector< vector<int> > ret;
    void dfs(TreeNode* root, int depth) {
        if (!root) return ;
        
        // 将当前节点加入解
        // 动态增加答案的数组数量
        if (ret.size() <= depth) ret.push_back(vector<int>());
        // 将当前节点加入对应的数组
        ret[ depth ].push_back(root -> val);
        
        // 处理子节点
        dfs(root -> left, depth + 1);    // 先左
        dfs(root -> right, depth + 1);   // 后右
        
        return ;
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        dfs(root, 0);
        return ret;
    }
};

登录发表评论 注册

反馈意见