问题:


给定一个二叉树,返回其节点值自底向上的层序遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

例如:
给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7
返回其自底向上的层序遍历为:

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

解答思路:

一、题目分析:本题要求对二叉树进行层序遍历,并将结果以自底向上的顺序返回。

二、主要思路:
1. 使用队列来实现层序遍历。
2. 从根节点开始,将其入队。
3. 进入循环,每次取出队列头部的节点,并将其值加入当前层的结果列表中。
4. 如果该节点有左右子节点,将它们入队。
5. 循环结束后,将当前层的结果列表添加到最终结果列表的头部。
6. 重复上述步骤,直到队列为空。

三、以下是修改后的 Java 代码:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeLevelOrderTraversalII {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode current = queue.poll();
                level.add(current.val);

                if (current.left!= null) {
                    queue.offer(current.left);
                }

                if (current.right!= null) {
                    queue.offer(current.right);
                }
            }

            result.add(0, level);
        }

        return result;
    }

    public static void main(String[] args) {
        // 构建二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        BinaryTreeLevelOrderTraversalII solution = new BinaryTreeLevelOrderTraversalII();
        List<List<Integer>> result = solution.levelOrderBottom(root);

        // 打印结果
        for (List<Integer> level : result) {
            System.out.println(level);
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}


(文章为作者在学习java过程中的一些个人体会总结和借鉴,如有不当、错误的地方,请各位大佬批评指正,定当努力改正,如有侵权请联系作者删帖。)

10-04 19:50