leetcode102：二叉树的层序遍历

题目链接

leetcode

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。
即逐层地，从左到右访问所有节点。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

// 二叉树结点的定义
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) {}
};

const int NULL_NODE = -1001;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    层次遍历

    时间复杂度：O(n)
        其中 n 为二叉树结点的个数，每个点进队出队各一次。
    空间复杂度：O(n)
        队列中元素的个数不超过 n 个。
*/
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }

        vector<vector<int>> res;
        queue<TreeNode*> q;
        q.push(root);
        // 从上向下一层层遍历
        while (!q.empty()) {
            int size = q.size(); // 每一层的结点个数
            vector<int> level;   // 每一层的结点值
            // 每一层从左向右遍历
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                level.push_back(node->val);
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            res.push_back(level);
        }
        return res;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {3, 9, 20, NULL_NODE, NULL_NODE, 15, 7};

    // 创建二叉树
    TreeNode* root = createTree(nums);
    levelOrderTraversal(root);

    // 层序遍历
    vector<vector<int>> result = solution.levelOrder(root);
    // 打印结果
    for (const auto& level : result) {
        for (int val : level) {
            cout << val << " ";
        }
        cout << endl;
    }

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

package main

import (
	"container/list"
	"fmt"
)

// 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 {
		return nil
	}
	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// 打印二叉树（层序遍历）
func printTree(root *TreeNode) string {
	if root == nil {
		return "[]"
	}
	result := []int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == nil {
			result = append(result, -1)
			continue
		}
		result = append(result, node.Val)
		queue = append(queue, node.Left)
		queue = append(queue, node.Right)
	}
	// 去掉尾部的 -1
	for len(result) > 0 && result[len(result)-1] == -1 {
		result = result[:len(result)-1]
	}
	return fmt.Sprintf("%v", result)
}

/*
	使用一个队列来实现层序遍历。
	首先将根节点入队，然后进入循环，取出队列当前大小的节点数量，
	将这些节点的值放入当前层的结果中，并将它们的非空左右子节点入队。
	重复这个过程，直到队列为空。

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    result := [][]int{}
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        size := len(queue)
        level := []int{}
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, level)
    }
    return result
}

// 思路同上，写法略不同
func levelOrder_1(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    result := make([][]int, 0)
    queue := list.New()
    queue.PushBack(root)

    for queue.Len() > 0 {
        size := queue.Len()
        level := make([]int, size)
        for i := 0; i < size; i++ {
            element := queue.Front()
            queue.Remove(element)
            node := element.Value.(*TreeNode)
            level[i] = node.Val
            if node.Left != nil {
                queue.PushBack(node.Left)
            }
            if node.Right != nil {
                queue.PushBack(node.Right)
            }
        }
        result = append(result, level)
    }
    return result
}

func main() {
    // 测试用例
	testCases := []struct {
		values   []int
		expected [][]int
	}{
		{
			values:   []int{3,9,20,-1,-1,15,7},
			expected: [][]int{{3}, {9,20}, {15,7}},
		},
		{
			values:   []int{1},
			expected: [][]int{{1}},
		},
		{
            values:   []int{},
			expected: nil,
		},
	}

	for i, tc := range testCases {
		root := createTree(tc.values)
		fmt.Printf("Test Case %d, Input: values = %v\n", i+1, printTree(root))
		result := levelOrder(root)
		resultStr := fmt.Sprintf("%v", result)
		expectedStr := fmt.Sprintf("%v", tc.expected)

		if resultStr == expectedStr {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
		}
	}
}