问题:
给定一个二叉树,返回其节点值自底向上的层序遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层序遍历为:
[
[15,7],
[9,20],
[3]
]
解答思路:
一、题目分析:本题要求对二叉树进行层序遍历,并将结果以自底向上的顺序返回。
二、主要思路:
1. 使用队列来实现层序遍历。
2. 从根节点开始,将其入队。
3. 进入循环,每次取出队列头部的节点,并将其值加入当前层的结果列表中。
4. 如果该节点有左右子节点,将它们入队。
5. 循环结束后,将当前层的结果列表添加到最终结果列表的头部。
6. 重复上述步骤,直到队列为空。
三、以下是修改后的 Java 代码:
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过程中的一些个人体会总结和借鉴,如有不当、错误的地方,请各位大佬批评指正,定当努力改正,如有侵权请联系作者删帖。)