[LeetCode-12]Binary Tree Level Order Traversal

最新推荐文章于 2025-05-20 08:09:36 发布

Mavs

最新推荐文章于 2025-05-20 08:09:36 发布

阅读量756

点赞数

分类专栏： Leetcode LeetCode Questions 文章标签： leetcode 二叉树 queue bfs

本文链接：https://blog.csdn.net/sbitswc/article/details/25945379

版权

Leetcode 同时被 2 个专栏收录

287 篇文章

订阅专栏

LeetCode Questions

178 篇文章

订阅专栏

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},

return its level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Two ways to resolve this problem:
1. Breadth first search
Initial an int variable to track the node count in each level and print level by level. And here need a QUEUE as a helper.
2. Depth first search
Rely on the recursion. Decrement level by one as you advance to the next level. When level equals 1, you’ve reached the given level and output them.
The cons is, DFS will revisit the node, which make it less efficient than BFS.

c++

vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int>> result;
    vector<TreeNode*> sta;
    if(root == NULL) return result;
    sta.push_back(root);
    int nextLevCou = 1;
    int index = 0;
    while(index < sta.size()){
        int curLevCou = nextLevCou;
        nextLevCou = 0;
        vector<int > level;
        for(int i = index; i<index+curLevCou; i++){
            root = sta[i];
            level.push_back(root->val);
            if(root->left != NULL){
                sta.push_back(root->left);
                nextLevCou++;
            }
            if(root->right !=NULL){
                sta.push_back(root->right);
                nextLevCou++;
            }

        }
        result.push_back(level);
        index = index+curLevCou;
    }
    return result;
    }

java

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		ArrayList<TreeNode> temp = new ArrayList<TreeNode>();
		if(root == null) return result;
		temp.add(root);
		int index = 0;
		int nextLevCount = 1;
		while(index<temp.size()){
			int curLevCount = nextLevCount;
			nextLevCount = 0;
			ArrayList<Integer> level = new ArrayList<Integer>();
			for(int i = index;i<index+curLevCount;i++){
				root = temp.get(i);
				level.add(root.val);
				if(root.left!=null){
					nextLevCount++;
					temp.add(root.left);
				}
				if(root.right!=null){
					nextLevCount++;
					temp.add(root.right);
				}
			}
			result.add(level);
			index+=curLevCount;
		}
		return result;
    }