算法:二叉树的层序遍历
算法 About 3,152 words要求
例如:以下二叉树按4 2 7 1 3 6 9
顺序输出,一层一层输出。
4
/ \
2 7
/ \ / \
1 3 6 9
广度优先搜索
根节点先入队列,出队列后将左右节点再加入队列中。
public List<Integer> bfs(Node root) {
if (root == null)
return null;
List<Integer> list = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
list.add(node.id);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return list;
}
深度优先搜索
定义List<List<Integet>>
第一层List
存储层数,第二层List<Integer>
存储每层的元素。
private List<List<Integer>> levelList = new ArrayList<>();
public void bfsRecursion(Node root, int level) {
if (root == null) {
return;
}
if (level >= levelList.size()) {
levelList.add(new ArrayList<>());
}
levelList.get(level).add(root.id);
bfsRecursion(root.left, level + 1);
bfsRecursion(root.right, level + 1);
}
完整代码
public class TreeBFSPrint {
public static void main(String[] args) {
TreeBFSPrint tree = new TreeBFSPrint();
int[] arr = {4, 2, 7, 1, 3, 6, 9};
for (int i : arr) {
Node node = new Node(i);
tree.add(node);
}
System.out.println(tree.root.id);
// System.out.println(tree.bfs(tree.root));
tree.bfsRecursion(tree.root, 0);
System.out.println(tree.levelList);
}
public Node root;
public List<Integer> bfs(Node root) {
if (root == null)
return null;
List<Integer> list = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
list.add(node.id);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return list;
}
private List<List<Integer>> levelList = new ArrayList<>();
public void bfsRecursion(Node root, int level) {
if (root == null) {
return;
}
if (level >= levelList.size()) {
levelList.add(new ArrayList<>());
}
levelList.get(level).add(root.id);
bfsRecursion(root.left, level + 1);
bfsRecursion(root.right, level + 1);
}
public void add(Node node) {
root = add(root, node);
}
public Node add(Node rootNode, Node node) {
if (rootNode == null) {
return node;
}
if (rootNode.id > node.id) {
rootNode.left = add(rootNode.left, node);
} else {
rootNode.right = add(rootNode.right, node);
}
return rootNode;
}
private static class Node {
public int id;
public Node left;
public Node right;
public Node(int id) {
this.id = id;
}
}
}
Views: 1,643 · Posted: 2021-02-21
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...