leetcode刷题——二叉树（1）

1、递归遍历二叉树

2、迭代法遍历二叉树（通过while循环）

3、二叉树的层序遍历

4、二叉树的层次遍历 II

5、二叉树的右视图

6、二叉树的层平均值

7、N叉树的层序遍历

8、在每个树行中找最大值

9、填充每个节点的下一个右侧节点指针

10、填充每个节点的下一个右侧节点指针II

11、二叉树的最大深度

12、二叉树的最小深度

二叉树有两种主要的形式：满二叉树和完全二叉树、二叉搜索树、二叉平衡树

遍历方式

深度优先遍历
- 前序遍历（递归法，迭代法）中左右
- 中序遍历（递归法，迭代法）左中右
- 后序遍历（递归法，迭代法）左右中
- 前中右代表中间节点的位置
广度优先遍历
- 层次遍历（迭代法）

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 继承vectorif (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有sizeQueue<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 removeFirstif(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叉树的层序遍历

力扣题目链接(opens new window)

给定一个 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、在每个树行中找最大值

力扣题目链接(opens new window)

您需要在二叉树的每一行中找到最大的值。

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有sizeQueue<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、填充每个节点的下一个右侧节点指针

力扣题目链接(opens new window)

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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有sizeQueue<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

力扣题目链接(opens new window)

这道题的答案和上一个一样，上一个题目是满二叉树，这道题的是普通二叉树

class Solution {public Node connect(Node root) {//queue方法 offer peek poll  linkedlist有sizeQueue<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、二叉树的最大深度

力扣题目链接(opens new window)

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

class Solution {public int maxDepth(TreeNode root) {//queue方法 offer peek poll  linkedlist有sizeQueue<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、二叉树的最小深度

力扣题目链接(opens new window)

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有sizeQueue<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;}
}