leetcode刷题——二叉树（1）
目录
二叉树有两种主要的形式：满二叉树和完全二叉树、二叉搜索树、二叉平衡树
遍历方式
- 深度优先遍历
- 前序遍历（递归法，迭代法）中左右
- 中序遍历（递归法，迭代法）左中右
- 后序遍历（递归法，迭代法）左右中
- 前中右代表中间节点的位置
- 广度优先遍历
- 层次遍历（迭代法）
1、递归遍历二叉树
-
确定递归函数的参数和返回值
-
确定终止条件
-
确定单层递归的逻辑
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(){};
TreeNode(int val){this.val=val;}
}
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preOrder(root,res);
return res;
}
//前序遍历：中左右
public void preOrder(TreeNode cur,List<Integer> res){
if(cur==null){return;}
res.add(cur.val);
preOrder(cur.left,res);
preOrder(cur.right,res);
}
//后序遍历：左右中
public void postOrder(TreeNode cur,List<Integer> res){
if(cur==null){return;}
postOrder(cur.left,res);
postOrder(cur.right,res);
res.add(cur.val);
}
//中序遍历：左中右
public void inOrder(TreeNode cur,List<Integer> res){
if(cur==null){return;}
inOrder(cur.left,res);
res.add(cur.val);
inOrder(cur.right,res);
}
}2、迭代法遍历二叉树（通过while循环）
class Solution {
//前序迭代：先把中间节点入栈，然后弹出再把右边的节点入栈，再把左节点入栈，才能保证弹出的顺序是中左右
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
Stack<TreeNode> ss=new Stack();
// stack方法 peek pop push empty 继承vector
if (root==null) return res;
TreeNode cur=root;
ss.push(cur);
while(!ss.empty()){
TreeNode node=ss.pop();
res.add(node.val);
if(node.right!=null) ss.push(node.right);
if(node.left!=null) ss.push(node.left);
}
return res;
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
Stack<TreeNode> ss=new Stack<>();
if(root==null) return res;
TreeNode cur=root;
//中序遍历，左中右
while(!ss.empty() || cur!=null){
//不断的把左节点入栈
if(cur!=null) {
ss.push(cur);
cur=cur.left;
}
//左节点为空，那就弹出当前的中间节点，然后把指针挪到右边节点
else{
cur=ss.pop();
res.add(cur.val);
cur=cur.right;
}
}
return res;
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
Stack<TreeNode> ss=new Stack<>();
if(root==null) return res;
TreeNode cur=root;
ss.push(cur);
while(cur!=null || !ss.empty()){
//左右中的顺序
//先遍历完左边的节点，同时要切断树之间的联系，免得下次重复添加节点
if(cur.left!=null){
ss.push(cur.left);
cur.left=null;
cur=ss.peek();
continue;
}
//遍历完右边的节点，同时要切断树之间的联系，免得下次重复添加节点
if(cur.right!=null){
ss.push(cur.right);
cur.right=null;
cur=ss.peek();
}
左右遍历结束后，就弹出中间节点，然后回到栈顶的下一个节点
else{
cur=ss.pop();
res.add(cur.val);
System.out.print(cur.val);
if(!ss.empty())
cur=ss.peek();
else{
cur=null;
}
}
}
return res;
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
Stack<TreeNode> ss=new Stack<>();
if(root==null) return res;
TreeNode cur=root;
ss.push(cur);
//前序遍历是中左右，那改变左右顺序变成 中右左 最后反转就是左右中后序遍历
while(!ss.empty()){
cur=ss.pop();
res.add(cur.val);
if(cur.left!=null) ss.push(cur.left);
if(cur.right!=null) ss.push(cur.right);
}
Collections.reverse(res);
return res;
}3、二叉树的层序遍历
class Solution {
public List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
//queue方法 offer peek poll linkedlist有size
Queue<TreeNode> qq=new LinkedList<>();
if(root==null) return res;
qq.offer(root);
while(qq.size()!=0){
//len代表每一层的节点数量
int len=qq.size();
List<Integer> tem=new ArrayList<>();
while(len>0){
TreeNode node=qq.poll();
tem.add(node.val);
if(node.left!=null) qq.offer(node.left);
if(node.right!=null) qq.offer(node.right);
len--;
}
res.add(tem);
}
return res;
}
}4、二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
Queue<TreeNode> qq=new LinkedList<>();
LinkedList<List<Integer>> res=new LinkedList<>();
//queue的运行类型是链表，但是还是只能使用queue定义的方法 offer add peek poll remove 多态
//LinkedList双链表实现 dequeue 和list 方法addFirst addLast getFirst removeFirst
if(root==null) return res;
qq.add(root);
while(!qq.isEmpty()){
List<Integer> tem=new LinkedList<>();
int len=qq.size();
while(len-->0){
TreeNode node=qq.poll();
tem.add(node.val);
if(node.left!=null) qq.add(node.left);
if(node.right!=null) qq.add(node.right);
}
res.addFirst(tem);
}
return res;
}
}5、二叉树的右视图
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Queue<TreeNode> qq=new LinkedList<>();
List<Integer> res=new LinkedList<>();
if(root==null) return res;
qq.offer(root);
while(!qq.isEmpty()){
int len=qq.size();
TreeNode node=null;
while(len-->0){
node=qq.poll();
if(node.left!=null) qq.offer(node.left);
if(node.right!=null) qq.offer(node.right);
}
//每一层都弹出，node保留的是最右边的值
res.add(node.val);
}
return res;
}
}6、二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res=new LinkedList<>();
Queue<TreeNode> qq=new LinkedList<>();
if(root==null) return res;
qq.offer(root);
while(!qq.isEmpty()){
int len=qq.size();
double sum=0;
int i=len;
while(i-->0){
TreeNode node=qq.poll();
sum+=node.val;
if(node.left!=null) qq.offer(node.left);
if(node.right!=null) qq.offer(node.right);
}
//每一层都弹出，node保留的是最右边的值
res.add(sum/len);
}
return res;
}
}7、N叉树的层序遍历
给定一个 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) {
Queue<Node> qq=new LinkedList<>();
List<List<Integer>> res=new LinkedList<>();
if(root==null) return res;
qq.offer(root);
while(!qq.isEmpty()){
int len=qq.size();
Node node=null;
List<Integer> tem=new LinkedList();
while(len-->0){
node=qq.poll();
tem.add(node.val);
if(node.children!=null){
for(Node nn:node.children){
qq.offer(nn);
}
}
}
//每一层都弹出，node保留的是最右边的值
res.add(tem);
}
return res;
}
}8、在每个树行中找最大值
您需要在二叉树的每一行中找到最大的值。
Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).
class Solution {
public List<Integer> largestValues(TreeNode root) {
//queue方法 offer peek poll linkedlist有size
Queue<TreeNode> qq=new LinkedList<>();
List<Integer> res=new ArrayList<>();
if(root==null) return res;
qq.offer(root);
while(qq.size()!=0){
//len代表每一层的节点数量
int len=qq.size();
int big=qq.peek().val;
while(len>0){
TreeNode node=qq.poll();
big=big>node.val?big:node.val;
if(node.left!=null) qq.offer(node.left);
if(node.right!=null) qq.offer(node.right);
len--;
}
res.add(big);
}
return res;
}
}9、填充每个节点的下一个右侧节点指针
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
/*
// 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) {
//queue方法 offer peek poll linkedlist有size
Queue<Node> qq=new LinkedList<>();
if(root==null) return null;
qq.offer(root);
while(qq.size()!=0){
//len代表每一层的节点数量
int len=qq.size();
while(len>0){
Node node=qq.poll();
if(node.left!=null) qq.offer(node.left);
if(node.right!=null) qq.offer(node.right);
len--;
if(len!=0){
node.next=qq.peek();
}
}
}
return root;
}
}10、填充每个节点的下一个右侧节点指针II
这道题的答案和上一个一样，上一个题目是满二叉树，这道题的是普通二叉树
class Solution {
public Node connect(Node root) {
//queue方法 offer peek poll linkedlist有size
Queue<Node> qq=new LinkedList<>();
if(root==null) return null;
qq.offer(root);
while(qq.size()!=0){
//len代表每一层的节点数量
int len=qq.size();
while(len>0){
Node node=qq.poll();
if(node.left!=null) qq.offer(node.left);
if(node.right!=null) qq.offer(node.right);
len--;
if(len!=0){
node.next=qq.peek();
}
}
}
return root;
}
}11、二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
class Solution {
public int maxDepth(TreeNode root) {
//queue方法 offer peek poll linkedlist有size
Queue<TreeNode> qq=new LinkedList<>();
if(root==null) return 0;
qq.offer(root);
int depth=0;
while(qq.size()!=0){
//len代表每一层的节点数量
int len=qq.size();
while(len>0){
TreeNode node=qq.poll();
if(node.left!=null) qq.offer(node.left);
if(node.right!=null) qq.offer(node.right);
len--;
}
depth++;
}
return depth;
}
}12、二叉树的最小深度
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
class Solution {
public int minDepth(TreeNode root) {
//queue方法 offer peek poll linkedlist有size
Queue<TreeNode> qq=new LinkedList<>();
if(root==null) return 0;
qq.offer(root);
int depth=0;
while(qq.size()!=0){
//len代表每一层的节点数量
int len=qq.size();
while(len>0){
TreeNode node=qq.poll();
if(node.left!=null) qq.offer(node.left);
if(node.right!=null) qq.offer(node.right);
len--;
if(node.left==null&&node.right==null){
return ++depth;
}
}
depth++;
}
return depth;
}
}原文地址：https://blog.csdn.net/hahahahanhanhan/article/details/140751470
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！