144.二叉树的前序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traversal(res,root);
return res;
}
public void traversal(List<Integer> res ,TreeNode root){
if(root == null){
return;
}
res.add(root.val);
traversal(res,root.left);
traversal(res,root.right);
}
}
145.二叉树的后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traversal(res,root);
return res;
}
public void traversal(List<Integer> list, TreeNode root){
if(root == null){
return;
}
traversal(list,root.left);
traversal(list,root.right);
list.add(root.val);
}
}
94.二叉树的中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traversal(res,root);
return res;
}
public void traversal(List<Integer> list,TreeNode root){
if(root == null){
return;
}
traversal(list,root.left);
list.add(root.val);
traversal(list,root.right);
}
}
102.二叉树的层序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
traversal(res,root,0);
return res;
}
public void traversal(List<List<Integer>> list,TreeNode root, int deep){
if(root == null){
return;
}
if(list.size() < deep+1){
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
traversal(list,root.left,deep+1);
traversal(list,root.right,deep+1);
}
}
107.二叉树的层次遍历倒序
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
traversal(res,root,0);
Collections.reverse(res);
return res;
}
public void traversal(List<List<Integer>> list,TreeNode root,int deep){
if(root == null){
return;
}
if(list.size() < deep+1){
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
traversal(list,root.left,deep+1);
traversal(list,root.right,deep+1);
}
}
199.二叉树的右视图
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
traversal(res,root,0);
List<Integer> result = new ArrayList<>();
for(List<Integer> list:res){
result.add(list.getLast());
}
return result;
}
public void traversal(List<List<Integer>> list,TreeNode root,int deep){
if(root == null){
return;
}
while(list.size() <deep+1){
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
traversal(list,root.left,deep+1);
traversal(list,root.right,deep+1);
}
}
637.二叉树的层平均值
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<List<Integer>> rest = new ArrayList<>();
List<Double> res = new ArrayList<>();
traversal(rest,root,0);
for(List<Integer> l :rest){
res.add(l.stream()
.mapToInt(Integer::intValue)
.average()
.orElse(0));
}
return res;
}
public void traversal(List<List<Integer>> list,TreeNode root,int deep){
if(root == null){
return;
}
if(list.size() < deep+1){
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
traversal(list,root.left,deep+1);
traversal(list,root.right,deep+1);
}
}
429.N叉树的层序遍历
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
traversal(res,root,0);
return res;
}
public void traversal(List<List<Integer>> list,Node root,int deep){
if(root == null){
return;
}
if(list.size() < deep+1){
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
for(Node node : root.children){
traversal(list,node,deep+1);
}
}
}
515.在每个树行中找最大值
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
traversal(res,root,0);
List<Integer> result = new ArrayList<>();
for(List<Integer> l : res){
result.add(l.stream().max(Integer::compare).orElse(0));
}
return result;
}
public void traversal(List<List<Integer>> list, TreeNode root, int deep){
if(root == null){
return;
}
if(list.size() < deep+1){
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
traversal(list,root.left,deep+1);
traversal(list,root.right,deep+1);
}
}
116.填充每个节点的下一个右侧节点指针
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root == null){
return root;
}
Queue<Node> nodeq = new LinkedList<>();
nodeq.add(root);
while(!nodeq.isEmpty()){
int size = nodeq.size();
for(int i = 0; i < size; i++){
Node node = nodeq.poll();
if(i < size - 1){
node.next = nodeq.peek();
}
if(node.left != null){
nodeq.add(node.left);
}
if(node.right != null){
nodeq.add(node.right);
}
}
}
return root;
}
}
104.二叉树的最大深度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
int leftH = maxDepth(root.left);
int rightH = maxDepth(root.right);
return Math.max(leftH,rightH) + 1;
}
}
111.二叉树的最小深度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
int leftH = minDepth(root.left);
int rightH = minDepth(root.right);
if(leftH == 0 || rightH == 0){
return Math.max(leftH,rightH) + 1;
}
return Math.min(leftH,rightH)+ 1;
}
}
文章来源地址https://www.toymoban.com/news/detail-836812.html
文章来源：https://www.toymoban.com/news/detail-836812.html
到了这里，关于二叉树相关算法需了解汇总-基础算法操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
