代码随想三刷二叉树篇1
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> list = new ArrayList();
pre(root,list);
return list;
}
public void pre(TreeNode root,List<Integer> list){
if(root==null){
return;
}
list.add(root.val);
pre(root.left,list);
pre(root.right,list);
}
}
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> list = new ArrayList();
pos(root,list);
return list;
}
public void pos(TreeNode root,List<Integer> list){
if(root==null){
return;
}
pos(root.left,list);
pos(root.right,list);
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> result = new ArrayList();
pos(root,result);
return result;
}
public void pos(TreeNode root,List<Integer> list){
if(root==null){
return;
}
pos(root.left,list);
list.add(root.val);
pos(root.right,list);
}
}
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) {
Deque<TreeNode> queue = new LinkedList();
List<List<Integer>> result = new ArrayList();
if(root==null){
return result;
}
queue.addLast(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList();
for(int i = 0;i<size;i++){
TreeNode temp = queue.removeFirst();
list.add(temp.val);
if(temp.left!=null){
queue.addLast(temp.left);
}
if(temp.right!=null){
queue.addLast(temp.right);
}
}
result.add(list);
}
return result;
}
}
107. 二叉树的层序遍历 II
题目
代码
/**
* 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>> result = new ArrayList();
Deque<TreeNode> queue = new LinkedList();
if(root==null){
return result;
}
queue.addLast(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList();
for(int i=0;i<size;i++){
TreeNode t = queue.removeFirst();
list.add(t.val);
if(t.left!=null){
queue.addLast(t.left);
}
if(t.right!=null){
queue.addLast(t.right);
}
}
result.add(0,list);
}
return result;
}
}
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<Integer> result = new ArrayList();
if(root==null){
return result;
}
Deque<TreeNode> queue = new LinkedList();
queue.addLast(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0;i<size;i++){
TreeNode t = queue.removeFirst();
if(t.left!=null){
queue.addLast(t.left);
}
if(t.right!=null){
queue.addLast(t.right);
}
if(i==size-1){
result.add(t.val);
}
}
}
return result;
}
}
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<Double> result = new ArrayList();
if(root==null){
return result;
}
Deque<TreeNode> queue = new LinkedList();
queue.addLast(root);
while(!queue.isEmpty()){
int size = queue.size();
double sum = 0;
for(int i=0;i<size;i++){
TreeNode t = queue.removeFirst();
sum += t.val;
if(t.left!=null){
queue.addLast(t.left);
}
if(t.right!=null){
queue.addLast(t.right);
}
}
result.add(sum/size);
}
return result;
}
}
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<Integer> result = new ArrayList();
if(root==null){
return result;
}
Deque<TreeNode> queue = new LinkedList();
queue.addLast(root);
while(!queue.isEmpty()){
int size = queue.size();
int num = Integer.MIN_VALUE;
for(int i=0;i<size;i++){
TreeNode t = queue.removeFirst();
num = Math.max(num,t.val);
if(t.left!=null){
queue.addLast(t.left);
}
if(t.right!=null){
queue.addLast(t.right);
}
}
result.add(num);
}
return result;
}
}
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) {
findDepth(root,1);
return maxDepth;
}
int maxDepth = 0;
public void findDepth(TreeNode root,int depth){
if(root==null){
return;
}
maxDepth = Math.max(maxDepth,depth);
findDepth(root.left,depth+1);
findDepth(root.right,depth+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;
}
pre(root,1);
return min;
}
int min = Integer.MAX_VALUE;
public void pre(TreeNode root,int depth){
if(root==null){
return;
}
if(root.left==null&&root.right==null){
min = Math.min(min,depth);
}
pre(root.left,depth+1);
pre(root.right,depth+1);
}
}
226. 翻转二叉树
题目
代码
/**
* 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 TreeNode invertTree(TreeNode root) {
if(root==null||(root.left==null&&root.right==null)){
return root;
}
TreeNode left= invertTree(root.left);
TreeNode right= invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
