递归的三要素
1.递归函数的参数和返回值
2.递归出口
3.单层递归的逻辑
144. 二叉树的前序遍历
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
/**
* 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> result = new ArrayList<>();
preoder(root,result);
return result;
}
public void preoder(TreeNode node,List<Integer> result){
if (node==null){
return;
}
result.add(node.val);//前序遍历:中、左、右
preoder(node.left,result);
preoder(node.right,result);
}
}
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
/**
* 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> result = new ArrayList();
inorder(root,result);
return result;
}
public void inorder(TreeNode node, List<Integer> result){
if(node==null){
return;
}
inorder(node.left,result);//中序遍历:左、中、右
result.add(node.val);
inorder(node.right,result);
}
}
145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。
/**
* 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> result = new ArrayList();
postorder(root,result);
return result;
}
public void postorder(TreeNode node,List<Integer> result){
if(node==null){
return;
}
postorder(node.left,result);//后序遍历:左、右、中
postorder(node.right,result);
result.add(node.val);
}
}
二叉树的迭代遍历
用栈操作,递归也是用栈实现的嘛????
144. 二叉树的前序遍历
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
/**
* 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> result = new ArrayList<>();//结果列表
Stack<TreeNode> stack = new Stack<>();
if(root==null){
return result;
}
stack.push(root);//先把根节点加到栈中去
while (!stack.empty()){
TreeNode node = stack.pop();//从栈中弹出一个结点来进行操作
result.add(node.val);//弹出的元素加到结果列表中
if(node.right!=null){
stack.push(node.right);//右孩子不空就进栈
}
if(node.left!=null){
stack.push(node.left);//左孩子不空就进栈
}
}
return result;
}
}
- 妙蛙种子吃了妙脆角,妙到家啦
145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。
/**
* 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> result = new ArrayList<>();//结果列表
Stack<TreeNode> stack = new Stack<>();
if(root==null){
return result;
}
stack.push(root);//先把根节点加到栈中去
while (!stack.empty()){
TreeNode node = stack.pop();//从栈中弹出一个结点来进行操作
result.add(node.val);//弹出的元素加到结果列表中
if(node.left!=null){
stack.push(node.left);//左孩子不空就进栈
}
if(node.right!=null){
stack.push(node.right);//右孩子不空就进栈
}
}
Collections.reverse(result);
return result;
}
}
Collections.reverse(result) 链表反转
- 这题和前序遍历十分相似,就是入栈顺序不一样,画图找一下顺序,改前序遍历的代码就可啦
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
- 中序遍历和前序遍历、后序遍历不一样的地方是,前序遍历(中左右)、后序遍历(左右中),中结点在两端,处理结点就是当前遍历的结点(从根节点开始遍历,从根节点开始处理)。而中序遍历的遍历从根节点开始,要处理的结点却是从最左侧的结点开始。
/**
* 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> result = new ArrayList<>();//结果列表
Stack<TreeNode> stack = new Stack<>();
if(root==null){
return result;
}
TreeNode cur = root;//取到根结点
while (cur != null || !stack.isEmpty()){
if (cur != null){
stack.push(cur);//放入栈中
cur = cur.left;//把当前结点的左孩子赋给当前结点
}else{
cur = stack.pop();//弹出栈中的结点
result.add(cur.val);//放入结果集中
cur = cur.right;//把当前结点的右孩子赋给当前结点(左边已经遍历完了,上一步也把中间放入结果集中,该右边了)
}
}
return result;
}
}
二叉树的层序遍历
也就是广度优先遍历啦
102.二叉树的层序遍历
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
/**
* 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<>();//外层链表
Queue<TreeNode> que = new LinkedList<>();//新建一个队列
if (root == null) {
return res;
}
que.add(root);//把根节点放入队列
while (!que.isEmpty()){
//当队列不为空时
ArrayList<Integer> item = new ArrayList<>();//内层链表
int size = que.size();//队列的大小
while (size>0){
TreeNode node = que.poll();//弹出当前结点
if(node.left!=null){que.add(node.left);}//把当前结点的左孩子加进去(如果有的话)
if(node.right!=null){que.add(node.right);}//把当前结点的右孩子加进去(如果有的话)
item.add(node.val);//当前结点加到链表
size--;
}
res.add(item);//内层链表加入到外层链表中
}
return res;
}
}
下面是一堆层序遍历的题
107. 二叉树的层序遍历 II
给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
/**
* 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<>();//外层链表
Queue<TreeNode> que = new LinkedList<TreeNode>();//队列
if(root==null)return res;
que.add(root);//把根结点放入队列
while (!que.isEmpty()){
List<Integer> item = new ArrayList<>();
int size = que.size();
while (size > 0) {
TreeNode node = que.poll();//队列中弹出一个结点
item.add(node.val);
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
res.add(item);
}
Collections.reverse(res);
return res;
}
}
199. 二叉树的右视图
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
/**
* 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<Integer> res = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root==null)return res;
que.add(root);//根结点不为空,放入队列
while (!que.isEmpty()){
List<Integer> item = new ArrayList<>();
int size = que.size();
while (size>0){
TreeNode node = que.poll();
item.add(node.val);
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
Integer i = item.get(item.size() - 1);
res.add(i);
}
return res;
}
}
637. 二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
/**
* 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<Double> res = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root==null)return res;
que.add(root);
while (!que.isEmpty()){
int size = que.size();
double x = 0;
double sum = 0;
int count = size;
while (size>0){
TreeNode node = que.poll();
sum += node.val;
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
x = sum/count;
res.add(x);
}
return res;
}
}
429. 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) {
List<List<Integer>> res = new ArrayList<>();//外层链表
Queue<Node> que = new LinkedList<>();//新建一个队列
if (root == null) {
return res;
}
que.add(root);//把根节点放入队列
while (!que.isEmpty()){
//当队列不为空时
ArrayList<Integer> item = new ArrayList<>();//内层链表
int size = que.size();//队列的大小
while (size>0){
Node node = que.poll();//弹出当前结点
//当前结点加到链表
if(node.children!=null){
for (Node child : node.children) {
que.add(child);
}
}
item.add(node.val);
size--;
}
res.add(item);//内层链表加入到外层链表中
}
return res;
}
}
- 添加子结点到队列的操作有点不一样
515. 在每个树行中找最大值
给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。
/**
* 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<Integer> res = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root==null){
return res;
}
que.add(root);
while(!que.isEmpty()){
int size = que.size();
int x = Integer.MIN_VALUE;
while(size>0){
TreeNode node = que.poll();
x = node.val>x ? node.val : x;
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
res.add(x);
}
return res;
}
}
116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
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<Node> que = new LinkedList<>();
if (root == null) {
return root;
}
que.add(root);
while (que.size() > 0) {
int size = que.size();
Node node = que.poll();
if (node.left != null) {que.add(node.left);}
if (node.right != null) {que.add(node.right);}
for (int i = 1; i < size; i++) {
Node next = que.poll();//弹出该层剩余元素
if (next.left != null) que.add(next.left);
if (next.right != null) que.add(next.right);
node.next = next;
node = next;
}
}
return root;
}
}
117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树
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<Node> que = new LinkedList<>();
if (root == null) {
return root;
}
que.add(root);
while (que.size() > 0) {
int size = que.size();
Node node = que.poll();
if (node.left != null) {que.add(node.left);}
if (node.right != null) {que.add(node.right);}
for (int i = 1; i < size; i++) {
Node next = que.poll();//弹出该层剩余元素
if (next.left != null) que.add(next.left);
if (next.right != null) que.add(next.right);
node.next = next;
node = next;
}
}
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) {
Queue<TreeNode> que = new LinkedList<>();//新建一个队列
if (root == null) {
return 0;
}
que.add(root);//把根节点放入队列
int count = 0;
while (!que.isEmpty()) {
//当队列不为空时
count++;
ArrayList<Integer> item = new ArrayList<>();//内层链表
int size = que.size();//队列的大小
while (size > 0) {
TreeNode node = que.poll();//弹出当前结点
if (node.left != null) {
que.add(node.left);
}//把当前结点的左孩子加进去(如果有的话)
if (node.right != null) {
que.add(node.right);
}//把当前结点的右孩子加进去(如果有的话)
size--;
}
}
return count;
}
}
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) {
Queue<TreeNode> que = new LinkedList<>();//新建一个队列
if (root == null) {
return 0;
}
que.add(root);//把根节点放入队列
int count = 0;
while (!que.isEmpty()) {
//当队列不为空时
count++;
ArrayList<Integer> item = new ArrayList<>();//内层链表
int size = que.size();//队列的大小
while (size > 0) {
TreeNode node = que.poll();//弹出当前结点
if (node.left != null) {
que.add(node.left);
}//把当前结点的左孩子加进去(如果有的话)
if (node.right != null) {
que.add(node.right);
}//把当前结点的右孩子加进去(如果有的话)
if(node.left==null&&node.right==null){
return count;
}
size--;
}
}
return count;
}
}
总结
-
通过今天的题目大致掌握二叉树的结构。深度优先遍历方面掌握前序、中序、后续的递归实现和迭代实现。掌握广度优先遍历的模板(写了十道层序遍历的题目,就算是小猪也会了????
-
今天的题目自己写出来的不多,除了最后几道改模板的题,不知道是因为天太冷还是头上戴的蝴蝶结封印了我的智慧的????