二叉树的遍历、N叉树的层序遍历
目录
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
前序遍历
// 用递归的方法进行先序遍历
public void Helper(TreeNode treeNode) {
returnlist.add(treeNode.val);
if (treeNode.left != null) {
Helper(treeNode.left);
}
if (treeNode.right != null) {
Helper(treeNode.right);
}
}
// 用非递归的方法进行先序遍历
public static void Helper(TreeNode treeNode) {
Stack<TreeNode> stack = new Stack<>();
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
returnlist.add(treeNode.val);
stack.push(treeNode);
treeNode = treeNode.left;
}
if(!stack.isEmpty()){
treeNode = stack.pop();
treeNode = treeNode.right;
}
}
}
中序遍历
//用递归1
class Solution {
public List <Integer> inorderTraversal(TreeNode root) {
List <Integer> res = new ArrayList <>();
helper(root, res);
return res;
}
public void helper(TreeNode root, List <Integer> res) {
if (root != null) {
if (root.left != null) {
helper(root.left, res);
}
res.add(root.val);
if (root.right != null) {
helper(root.right, res);
}
}
}
}
// 用递归的方法进行中序遍历
public void Helper(TreeNode treeNode) {
if (treeNode.left != null) {
Helper(treeNode.left);
}
returnlist.add(treeNode.val);
if (treeNode.right != null) {
Helper(treeNode.right);
}
}
// 用非递归的方法进行中序遍历
public void Helper(TreeNode treeNode) {
Stack<TreeNode> stack = new Stack<TreeNode>();
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
stack.push(treeNode);
treeNode = treeNode.left;
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
returnlist.add(treeNode.val);
treeNode = treeNode.right;
}
}
}
递归的时间空间复杂度
栈的时间空间复杂度
不建议用stack
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List < Integer > res = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}后续遍历
// 用递归的方法进行后序遍历
public void Helper(TreeNode treeNode) {
if (treeNode.left != null) {
Helper(treeNode.left);
}
if (treeNode.right != null) {
Helper(treeNode.right);
}
returnlist.add(treeNode.val);
}
//后序遍历非递归：使用了先序遍历的知识，先序遍历是根->左->右，后序遍历是左->右->根，对于list的添加顺序可以变成在队列头添加（根->右->左），这样队列添加完就是左->右->根的顺序了
public static List<Integer> postorderTraversal_2(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if(root == null)
{
return ans;
}
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
stack.push(cur);
while(!stack.empty()){
cur = stack.pop();
if(cur.left != null){
stack.add(cur.left);
}
if(cur.right != null){
stack.add(cur.right);
}
ans.add(0, cur.val);
}
return ans;
}
从上往下打印二叉树
递归
static List<List<Integer>> levels = new ArrayList<>();
public static List<List<Integer>> levelOrder(TreeNode root) {
if (root == null){
return levels;
}
helper(root, 0);
return levels;
}
public static void helper(TreeNode node, int level) {
// start the current level
if (levels.size() == level) {
levels.add(new ArrayList<>());
}
// fulfil the current level
levels.get(level).add(node.val);
// process child nodes for the next level
if (node.left != null) {
helper(node.left, level + 1);
}
if (node.right != null){
helper(node.right, level + 1);
}
}
迭代 队列
// 二叉树按层遍历，使用队列
public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> arr = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if (root == null)
{
return arr;
}
deque.add(root);
// 先将根节点读入队列
while(!deque.isEmpty()){
// 当队列不为空时，就取出队列的第一个结点，并将它的孩子结点加入队列。
TreeNode t = deque.pop();
arr.add(t.val);
// 按层将元素加入arr数组
if(t.left != null)
{
deque.add(t.left);
}
if(t.right != null)
{
deque.add(t.right);
}
}
return arr;
}
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<List<Integer>>();
if (root == null) return levels;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int level = 0;
while ( !queue.isEmpty() ) {
// start the current level
levels.add(new ArrayList<Integer>());
// number of elements in the current level
int level_length = queue.size();
for(int i = 0; i < level_length; ++i) {
TreeNode node = queue.remove();
// fulfill the current level
levels.get(level).add(node.val);
// add child nodes of the current level
// in the queue for the next level
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
// go to next level
level++;
}
return levels;
}
二叉树倒着遍历
4
2 7
1 3 5 6 遍历顺序为4 7 6 5 2 3 1
public static List<Integer> postorderTraversal_2(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if(root == null)
{
return ans;
}
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
stack.push(cur);
while(!stack.empty()){
cur = stack.pop();
if(cur.left != null){
stack.add(cur.left);
}
if(cur.right != null){
stack.add(cur.right);
}
ans.add(cur.val);
}
return ans;
}
二叉树自底向上的层次遍历
递归
static List<List<Integer>> levels = new ArrayList<>();
static List<List<Integer>> returnLevels = new ArrayList<>();
public static List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null){
return levels;
}
helper(root, 0);
for (int i = levels.size()-1; i >=0 ; i--) {
returnLevels.add(levels.get(i));
}
return returnLevels;
}
private static void helper(TreeNode node, int level) {
// start the current level
if (levels.size() == level) {
levels.add(new ArrayList<>());
}
levels.get(level).add(node.val);
if (node.left != null) {
helper(node.left, level + 1);
}
if (node.right != null){
helper(node.right, level + 1);
}
}
Bfs
public List<List<Integer>> levelOrderBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> ans = new LinkedList<List<Integer>>();
if (root == null)
return ans;
queue.offer(root);
while (!queue.isEmpty()) {
int levelNum = queue.size(); // 当前层元素的个数
List<Integer> subList = new LinkedList<Integer>();
for (int i = 0; i < levelNum; i++) {
TreeNode curNode = queue.poll();
if (curNode != null) {
subList.add(curNode.val);
queue.offer(curNode.left);
queue.offer(curNode.right);
}
}
if (subList.size() > 0) {
ans.add(0, subList);
}
}
return ans;
}
二叉树的锯齿形层次遍历
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
递归
static List<List<Integer>> levels = new ArrayList<>();
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null){
return levels;
}
helper(root, 0);
return levels;
}
private static void helper(TreeNode node, int level) {
if (node == null) {
return;
}
if (levels.size() == level) {
levels.add(new ArrayList<>());
}
if(level % 2 ==0){
levels.get(level).add(node.val);
}else {
levels.get(level).add(0,node.val);
}
helper(node.left, level + 1);
helper(node.right, level + 1);
}
Bfs
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
int depth = 0;
while (!queue.isEmpty()) {
List<Integer> tmp = new LinkedList<>();
int cnt = queue.size();
for (int i = 0; i < cnt; i++) {
TreeNode node = queue.poll();
// System.out.println(node.val);
if (depth % 2 == 0) tmp.add(node.val);
else tmp.add(0, node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
res.add(tmp);
depth++;
}
return res;
}
}
二叉树的右视图
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> returnList = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
if(root == null){
return returnList;
}
helper(root,0);
return returnList;
}
public void helper(TreeNode root,int index){
if(root == null){
return;
}
if(index== returnList.size()){
returnList.add(root.val);
}
if(root.right != null){
helper(root.right,index+1);
}
if(root.left != null){
helper(root.left,index+1);
}
}
}
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res=new ArrayList<>();
if(root==null) {
return res;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int cnt=queue.size();
while(cnt-->0){
// y-->0在java中是什莫意思
// 先比较（y--）是否大于0，再让y=y-1，
// 如果是--y>0,就是先让y=y-1,再比较现在的y值是否大于0
TreeNode node=queue.poll();
if(node.left!=null) {
queue.offer(node.left);
}
if(node.right!=null) {
queue.offer(node.right);
}
if(cnt==0) {
res.add(node.val);
}
}
}
return res;
}
看一下是不是每一层第一次访问到的结点
二叉树的左视图
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<>();
rightSideView(root,list,0);
return list;
}
public void rightSideView(TreeNode root, List<Integer> list ,int level) {
if (root == null) {
return;
}
if (level == list.size()) {
list.add(root.val);
}
rightSideView(root.right,list,level+1);
rightSideView(root.left,list,level + 1);
}
public List<Integer> rightSideView(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> result = new ArrayList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
//对每一行操作
while(size > 0) {
TreeNode current = queue.poll();
if (current.left!=null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
size --;
//表示是每一行的最后一个
if (size == 0) {
result.add(current.value);
}
}
}
return result;
}public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(3);
TreeNode node3 = new TreeNode(5);
TreeNode node4 = new TreeNode(4);
root.left = node1;
root.right = node2;
node1.right = node3;
node2.right = node4;
LeftView(root);
}
public static void LeftView(TreeNode node) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(node);
//设置 size 和 child 两个标记，child在循环中会变，size不会变，作为循环条件
//第一层只有根节点1个，所以size = 1
int size = 1;
//记录孩子数
int child;
while (!queue.isEmpty()) {
//初始化孩子数为 0
child = 0;
for (int i = 0; i < size; i++) {
TreeNode node1 = queue.poll();
// i = 0,说明是该层第一个结点
if (i == 0) {
System.out.println(node1.val);
}
if (node1.left != null) {
queue.offer(node1.left);
child++;
}
if (node1.right != null) {
queue.offer(node1.right);
child++;
}
}
size = child;
}
}
N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[
[1],
[3,2,4],
[5,6]
]
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
方法三：递归
算法：
我们可以使用递归来解决这个问题，通常我们不能使用递归进行广度优先搜索。这是因为广度优先搜索基于队列，而递归运行时使用堆栈，适合深度优先搜索。但是在本题中，我们可以以不同的顺序添加到最终列表中，只要我们知道节点在哪一层并确保在那一层的列表顺序正确就可以了。
public class levelOrder {
public static void main(String[] args) {
}
static List<List<Integer>> returnList = new ArrayList<>();
public static List<List<Integer>> levelOrder(Node root) {
if(root == null){
return returnList;
}
if(root.children == null){
returnList.get(0).add(root.val);
return returnList;
}
helper(root,0);
return returnList;
}
private static void helper(Node root,int index) {
if (returnList.size() == index) {
returnList.add(new ArrayList<>());
}
returnList.get(index).add(root.val);
for (int i = 0; i <root.children.size() ; i++) {
helper(root.children.get(i),index +1);
}
}
}
方法一：利用队列实现广度优先搜索
// This code is a modified version of the code posted by
// #zzzliu on the discussion forums.
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
level.add(node.val);
queue.addAll(node.children);
}
result.add(level);
}
return result;
}
}
京公网安备 11010502036488号