Level Traversal
level(階層)ごとに探索を進める
個人的には二重配列で階層ごとに配列を作るやり方が直感的で理解しやすかった
個人的にはこの方のコード(Ruby)が分かりやすかった
上記リンク掲載のコードをもうちょい簡潔にするとこう
code:solution.rb
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val)
# @val = val
# @left, @right = nil, nil
# end
# end
# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
traverse(root, 0, [])
end
def traverse(node, level, ans)
return [] if node.nil?
traverse(node.left, level+1, ans)
traverse(node.right, level+1, ans)
ans
end
code:solution.cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
typedef vector<vector<int>> ints;
class Solution {
public:
ints levelOrder(TreeNode* root) {
ints ans = {};
return traverse(root, 0, ans);
}
ints traverse(TreeNode* node, int level, ints& ans) {
if (!node) return ans;
if (level < ans.size()) {
ans.at(level).push_back(node->val);
} else {
ans.push_back({node->val});
};
traverse(node->left, level+1, ans);
traverse(node->right, level+1, ans);
return ans;
}
};