第六章 二叉树part01
理论基础
需要了解 二叉树的种类，存储方式，遍历方式 以及二叉树的定义
文章讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
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;
}
}
递归遍历 （必须掌握）
二叉树的三种递归遍历掌握其规律后，其实很简单
题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html
前序：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
traversal(root, list);
return list;
}
public void traversal(TreeNode root, List<Integer> list){
if(root == null){
return;
}
list.add(root.val);
// traversal(root, list);当前做操作就行
traversal(root.left, list);
traversal(root.right, list);
}
}
后序：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
traversal(root, list);
return list;
}
public void traversal(TreeNode root, List<Integer> list){
if(root == null){
return;
}
traversal(root.left, list);
traversal(root.right, list);
list.add(root.val);
}
}
中序：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
traversal(root, list);
return list;
}
public void traversal(TreeNode root, List<Integer> list){
if(root == null){
return;
}
traversal(root.left, list);
list.add(root.val);
traversal(root.right, list);
}
}
迭代遍历 （基础不好的录友，迭代法可以放过）
题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html
错误前序遍历：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
traversal(root, list);
return list;
}
public void traversal(TreeNode root, List<Integer> list){
if(root == null){
return;
}
traversal(root.left, list);
list.add(root.val);
traversal(root.right, list);
}
}
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> deq = new LinkedList<>();
List<Integer> list = new ArrayList<>();
deq.push(root);
if (root == null) {
return list;
}// 特殊情况的判断
while(!deq.isEmpty()){
TreeNode cur = deq.poll();
list.add(cur.val);
if(cur.right != null){
deq.push(cur.right);
}
if(cur.left != null){
deq.push(cur.left);
}
}
return list;
}
}
后序遍历：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> deq = new LinkedList<>();
ArrayList<Integer> list = new ArrayList<>();
deq.push(root);
if (root == null) {
return list;
}
while(!deq.isEmpty()){
TreeNode cur = deq.poll();
list.add(cur.val);
if(cur.left != null){
deq.push(cur.left);
}
if(cur.right != null){
deq.push(cur.right);
}
}
Collections.reverse(list);
return list;
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> deq = new LinkedList<>();
ArrayList<Integer> list = new ArrayList<>();
TreeNode cur = root;
while(!deq.isEmpty() || cur != null){
if(cur != null){
deq.push(cur);
cur = cur.left;
}else{
cur = deq.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
统一迭代 （基础不好的录友，迭代法可以放过）
这是统一迭代法的写法， 如果学有余力，可以掌握一下 略
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
if (node.right!=null) st.push(node.right); // 添加右节点（空节点不入栈）
st.push(node); // 添加中节点
st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
if (node.left!=null) st.push(node.left); // 添加左节点（空节点不入栈）
} else { // 只有遇到空节点的时候，才将下一个节点放进结果集
st.pop(); // 将空节点弹出
node = st.peek(); // 重新取出栈中元素
st.pop();
result.add(node.val); // 加入到结果集
}
}
return result;
}
}
层序遍历
看完本篇可以一口气刷十道题，试一试， 层序遍历并不难，大家可以很快刷了十道题。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Deque<TreeNode> deq = new LinkedList<>();
if(root != null){
deq.addLast(root);
}
while(!deq.isEmpty()){
int size = deq.size();
List<Integer> lt = new ArrayList<>();
int i = 0;
while(i < size){
TreeNode cur = deq.removeFirst();
lt.add(cur.val);
if(cur.left != null){deq.addLast(cur.left);}
if(cur.right != null){deq.addLast(cur.right);}
i ++;
}
list.add(lt);
}
return list;
}
}
反序层次遍历：
List<List<Integer>> rlist = new ArrayList<>();
for(int i = list.size() - 1; i >= 0; i --){
rlist.add(list.get(i));
}
return rlist;
Collections.reverse(list);//返回值是空 在原集合上进行的操作
右视图：
List<Integer> res = new ArrayList<>();
for(List<Integer> l : list){
int size = l.size();
res.add(l.get(size-1));
}
return res;
平均值：
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
Deque<TreeNode> deq = new LinkedList<>();
if(root != null){
deq.addLast(root);
}
while(!deq.isEmpty()){
int size = deq.size();
List<Integer> lt = new ArrayList<>();
int i = 0;
double count = 0;
while(i < size){
TreeNode cur = deq.removeFirst();
lt.add(cur.val);
count += cur.val;
if(i == size - 1){
result.add(count / size);
}
if(cur.left != null){deq.addLast(cur.left);}
if(cur.right != null){deq.addLast(cur.right);}
i ++;
}
}
return result;
}
}
n叉树
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> list = new ArrayList<>();
Deque<Node> deq = new LinkedList<>();
if(root != null){
deq.addLast(root);
}
while(!deq.isEmpty()){
int size = deq.size();
List<Integer> lt = new ArrayList<>();
int i = 0;
while(i < size){
Node cur = deq.removeFirst();
lt.add(cur.val);
for(Node node : cur.children){
if(node != null){deq.addLast(node);}
}
i ++;
}
list.add(lt);
}
return list;
}
}
每层最小值：
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> deq = new LinkedList<>();
if (root != null) {
deq.addLast(root);
}
while (!deq.isEmpty()) {
int size = deq.size();
int max = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
TreeNode cur = deq.removeFirst();
if (cur.val > max) max = cur.val;
if (cur.left != null) deq.addLast(cur.left);
if (cur.right != null) deq.addLast(cur.right);
}
list.add(max);
}
return list;
}
}
完美二叉树指针：
class Solution {
public Node connect(Node root) {
Deque<Node> deq = new LinkedList<>();
if (root != null) {
deq.addLast(root);
}
while (!deq.isEmpty()) {
int size = deq.size();
List<Node> lt = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node cur = deq.removeFirst();
lt.add(cur);
if (cur.left != null) deq.addLast(cur.left);
if (cur.right != null) deq.addLast(cur.right);
}
lt.add(null);
for(int i = 0; i < lt.size() - 1; i ++){
lt.get(i).next = lt.get(i + 1);
}
}
return root;
}
}
最大深度
class Solution {
public int maxDepth(TreeNode root) {
int deep = 0;
Deque<TreeNode> deq = new LinkedList<>();
if (root != null) {
deq.addLast(root);
}
while (!deq.isEmpty()) {
int size = deq.size();
for (int i = 0; i < size; i++) {
TreeNode cur = deq.removeFirst();
if (cur.left != null) deq.addLast(cur.left);
if (cur.right != null) deq.addLast(cur.right);
}
deep ++;
}
return deep;
}
}
最小深度：
class Solution {
public int minDepth(TreeNode root) {
int deep = 0;
boolean flag = false;
Deque<TreeNode> deq = new LinkedList<>();
if (root != null) {
deq.addLast(root);
}
while (!deq.isEmpty()) {
int size = deq.size();
for (int i = 0; i < size; i++) {
TreeNode cur = deq.removeFirst();
if (cur.left == null && cur.right == null){
flag = true;
}
if (cur.left != null) deq.addLast(cur.left);
if (cur.right != null) deq.addLast(cur.right);
}
deep ++;
if(flag) break;
}
return deep;
}
}
