讨论/《广度优先搜索》 - 例题:二叉树的层序遍历/
《广度优先搜索》 - 例题:二叉树的层序遍历
共 15 个回复
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        q = deque([root])
        res = []
        while q :
            l = []
            for i in range(len(q)) :
                t = q.popleft()
                l.append(t.val)
                if t.left : q.append(t.left)
                if t.right : q.append(t.right)
            res.append(l)
        return res
3

C++

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        int tt = 0, hh = 0;
        arr[0] = root;
        vector<vector<int>> ans;

        while(tt <= hh){
            int size = (hh - tt + 1 + MOD) % MOD;
            vector<int> tmp;
            while(size --){
                TreeNode *cur = arr[tt ++];
                if(cur == nullptr)
                    continue;
                tmp.push_back(cur -> val);
                arr[++ hh] = cur -> left;
                arr[++ hh] = cur -> right;
            }
            if(tmp.size())
                ans.push_back(tmp);   
        }
        return ans;
    }

private:
    static const int MOD = 10001;
    TreeNode *arr[MOD];
};
2

c++

/**
 * 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>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root==nullptr)return ans;
        TreeNode* tn=root;
        queue<TreeNode*> layer;
        layer.push(tn);
        while(!layer.empty()){
            vector<int> this_layer;
            //获取当前层级的队列长度
            int qsize=layer.size(); 
            //循环遍历当前层级的所有节点
            for(int tmp=0;tmp<qsize;tmp++){
                tn=layer.front();
                layer.pop();
                this_layer.push_back(tn->val);
                //将下一层级的所有节点从左往右添加至队列尾
                if(tn->left)layer.push(tn->left);
                if(tn->right)layer.push(tn->right);
            }
            ans.push_back(this_layer);
        }
        return ans;
    }
};
1

哦,对,写错了,多谢指正

1

Python
1、递归实现:

def levelOrder(root):
    """
    递归
    :param root:
    :return:
    """
    outcome = []

    def bfs(nodes):
        if not nodes:
            return
        next_nodes = []
        temp = []
        for node in nodes:
            temp.append(node.val)
            if node.left:
                next_nodes.append(node.left)
            if node.right:
                next_nodes.append(node.right)
        outcome.append(temp)
        bfs(next_nodes)
    bfs([root])
    return outcome

2、队列实现

def levelOrder_1(root):
    """
    使用队列来广度优先遍历
    :param root:
    :return:
    """
    que = queue.deque()
    que.append(root)
    outcome = []
    while que:
        temp = []
        length = len(que)
        for i in range(length):
            node = que.popleft()
            if node.left:
                que.append(node.left)
            if node.right:
                que.append(node.right)
            temp.append(node.val)
        outcome.append(temp)
    return outcome
1
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            res.add(level);
        }
        return res;
    }
}
1
/**
 * 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>> levelOrder(TreeNode* root) {
        //同一层的需要装在一个数组里
        queue<TreeNode*> Q;
        int curSize = 0;
        vector<vector<int>> res;
        vector<int> temp; 
        if(root == nullptr) return {};
        Q.push(root);
        while(!Q.empty()) {
            curSize = Q.size();
            temp.clear();
            for(int i = 0; i < curSize; i++) {
                TreeNode* node = Q.front();
                Q.pop();
                temp.emplace_back(node->val);
                if(node->left) {
                    Q.push(node->left);
                }
                if(node->right) {
                    Q.push(node->right);
                }
            }
            res.push_back(temp);
        }
        return res;
    }
};

GO语言的实现

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}

	ret := make([][]int, 0)
	var q *Queue = new(Queue)
	q.enqueue(root)
	for !q.isEmpty() {
		length := q.size()
		row := make([]int, 0)
		for i := 0; i < length; i++ {
			curNode := q.dequeue()
			row = append(row, curNode.Val)
			if curNode.Left != nil {
				q.enqueue(curNode.Left)
			}
			if curNode.Right != nil {
				q.enqueue(curNode.Right)
			}
		}
		ret = append(ret, row)
	}
	return ret
}

type Queue struct {
	values []*TreeNode
}

func (q *Queue) enqueue(ele *TreeNode) {
	q.values = append(q.values, ele)
}

func (q *Queue) dequeue() *TreeNode {
	if len(q.values) == 0 {
		return nil
	}

	ret := q.values[0]
	q.values = q.values[1:]
	return ret
}

func (q *Queue) isEmpty() bool {
	return len(q.values) == 0
}

func (q *Queue) size() int {
	return len(q.values)
}

【关于Python】一开始用的 queue 包里的Queue(), 速度奇慢。后来换成 list 就好多了。

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        node_queue = []
        if root == None: return res
        node_queue.append(root)
        while node_queue:
            layer_nodes = []
            q_len = len(node_queue)
            for i in range(q_len):
                father_node = node_queue.pop(0)
                layer_nodes.append(father_node.val)
                if father_node.left:
                    node_queue.append(father_node.left)
                if father_node.right:
                    node_queue.append(father_node.right)
            res.append(layer_nodes)
        return res
type queenItem struct {
     Val *TreeNode
     Next *queenItem
 }

type Queen struct{
    Head *queenItem
    Tail *queenItem
    Size int
}
func (q *Queen) Append(n *TreeNode) *Queen {
    item := &queenItem{
        Val: n,
    }
    q.Size++
    if q.Head == nil {
        q.Head = item
        q.Tail = item
    } else {
        q.Tail.Next = item
        q.Tail = item
    }
    return q
}

func (q *Queen) Pop() *TreeNode {
    q.Size--
    if q.Head == nil {
        panic("empty queen!")
    }
    header := q.Head
    q.Head = q.Head.Next
    return header.Val
}

func (q *Queen) HasNext() bool {
    return q.Head != nil
}


func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return make([][]int, 0)
    }
    q := &Queen{}
	q.Append(root)
	results := make([][]int, 0)
	for q.HasNext() {
		levelResults := make([]int, 0)
		n := q.Size
		for i := 0; i < n; i++ {
			top := q.Pop()
			levelResults = append(levelResults, top.Val)
			if top.Left != nil {
				q.Append(top.Left)
			}
			if top.Right != nil {
				q.Append(top.Right)
			}
		}
		results = append(results, levelResults)
	}
	return results
}