TechNomads

BFS（广度优先搜索）Java

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

                Queue<TreeNode> queue = new ArrayDeque<>();
                if (root != null) {
                    queue.add(root);
                }

                while(!queue.isEmpty()) {
                    int n = queue.size();

                    List<Integer> level = new ArrayList<>();
                    for(int i = 0; i<n; i++) {
                        TreeNode node = queue.poll();
                        level.add(node.val);
                        if (node.left != null) {
                            queue.add(node.left);
                        }
                        if (node.right != null) {
                            queue.add(node.right);
                        }
                    }
                    res.add(level);
                }
                return res;
    }

BFS GO写法

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

    // 总队列
    queue := []*TreeNode{root}

    for len(queue) > 0 {

        // 临时队列，保存每层的结点
        tmpQueue := []*TreeNode{}
        tmpRes := []int{}
        for j := 0; j < len(queue); j++ {
            node := queue[j]
            tmpRes = append(tmpRes, node.Val)
            if node.Left != nil {
                tmpQueue = append(tmpQueue, node.Left)
            }

            if node.Right != nil {
                tmpQueue = append(tmpQueue, node.Right)
            }
        }

        // 处理完一层，处理下一层
        queue = tmpQueue
        res = append(res, tmpRes)
    }

    return res
}

运行结果：

DFS（深度优先搜索）GO

采用递归的方式：

var res [][]int
func levelOrder(root *TreeNode) [][]int {
    if root == nil{
        return nil
    }
    res = make([][]int, 0)
    dfs(root, 0)
    return res
}

func dfs(root *TreeNode, level int){
    if root == nil{
        return
    }
    if level == len(res){
        res = append(res, []int{})
    }
    res[level] = append(res[level], root.Val)
    dfs(root.Left, level+1)
    dfs(root.Right,level+1)
}

运行结果：