Java实现Leetcode题（二叉树）

Leetcode144(前序遍历)

//递归public static List inorderTraversal(TreeNode root){List list = new ArrayList();inorder(root,list);return list;}public static void inorder(TreeNode root,List list) {if(root==null) {return;}list.add(root.val);inorder(root.left,list);inorder(root.right,list);}//迭代public static List preorderTraversal(TreeNode root){List list = new ArrayList();Deque de = new LinkedList();if(root==null) {return list;}de.addFirst(root);while(!de.isEmpty()) {TreeNode temp = de.peekFirst();de.pollFirst();list.add(temp.val);if(temp.right!=null) {de.addFirst(temp.right);}if(temp.left!=null) {de.addFirst(temp.left);}}return list;}

Leetcode145（后序遍历）

//迭代法public static List postorderTraversal(TreeNode root){List list = new ArrayList();Deque de = new LinkedList();if(root==null) {return list;}de.addFirst(root);while(!de.isEmpty()) {TreeNode temp = de.peekFirst();de.pollFirst();list.add(temp.val);if(temp.left!=null) {de.addFirst(temp.left);}if(temp.right!=null) {de.addFirst(temp.right);}}Collections.reverse(list);return list;} //递归public static List postorderTraversal(TreeNode root){List list = new ArrayList();postorder(root,list);return list;}public static void postorder(TreeNode root,List list) {postorder(root.left,list);postorder(root.right,list);list.add(root.val);}

Leetcode94（中序遍历）

//迭代public static List inorderTraversal(TreeNode root){List list = new ArrayList();Deque de = new LinkedList();if(root == null) {return list;}TreeNode cur = root;while(cur!=null||!de.isEmpty()) {if(cur!=null) {de.addFirst(cur);cur = cur.left;}else {cur = de.peekFirst();list.add(cur.val);de.pollFirst();cur = cur.right;}}return list;}//递归public static List inorderTraveral(TreeNode root){List list = new ArrayList();inorder(root,list);return list;}public static void inorder(TreeNode root,Listlist) {if(root==null) {return;}inorder(root.left,list);list.add(root.val);inorder(root.right,list);}

Leetcode102(层序遍历)

 public List<List> levelOrder(TreeNode root) {List<List> result = new LinkedList();Deque de = new LinkedList();if(root == null){return result;}de.add(root);while(!de.isEmpty()){int size = de.size();List list = new LinkedList();while(size-->0){TreeNode temp =de.pollFirst();list.add(temp.val);if(temp.left!=null){de.addLast(temp.left);}if(temp.right!=null){de.addLast(temp.right);}}result.add(list);}return result;}

Leetcode107（层序遍历II）

public List<List> levelOrderBottom(TreeNode root) {List<List> result = new LinkedList();Deque de = new LinkedList();if(root == null){return result;}de.add(root);while(!de.isEmpty()){int size = de.size();List list = new LinkedList();while(size-->0){TreeNode temp =de.pollFirst();list.add(temp.val);if(temp.left!=null){de.addLast(temp.left);}if(temp.right!=null){de.addLast(temp.right);}}result.add(list);} Collections.reverse(result); return result;}

Leetcode199(二叉树的右视图)

public class LeetCode199 { public List rightSideView(TreeNode root) { List list = new LinkedList(); Deque de = new LinkedList(); if(root==null) { return list; } de.add(root); while(!de.isEmpty()) { int size = de.size(); while(size-->0) { TreeNode temp = de.pollFirst(); if(size==0) { list.add(temp.val); } if(temp.left!=null){de.addLast(temp.left);}if(temp.right!=null){de.addLast(temp.right);} }} return list; }}

LeetCode637（二叉树的层平均值）

public class LeetCode637 {public List averageOfLevels(TreeNode root) {List result = new LinkedList();Deque de = new LinkedList();if(root==null) {return result;}de.add(root);while(!de.isEmpty()) {int size = de.size();int num = size;double sum = 0;while(size-->0) {TreeNode temp = de.peekFirst();de.pollFirst();sum+=temp.val;if(temp.left!=null) {de.addLast(temp.left);}if(temp.right!=null) {de.addLast(temp.right);}}double total = sum/num;result.add(total);}return result;}}

LeetCode429（N叉树的层序遍历）

package tree;import java.util.Deque;import java.util.LinkedList;import java.util.List;public class LeetCode429 {public List<List> levelOrder(Node root) {List<List> result = new LinkedList();Deque de = new LinkedList();if(root == null) {return result;}de.add(root);while(!de.isEmpty()) {int size = de.size();List list = new LinkedList();while(size-->0) {Node temp = de.pollFirst();list.add(temp.val);if(temp.children!=null) {for(int i = 0;i<temp.children.size();i++) {de.addLast(temp.children.get(i));}}}result.add(list);}return result;}}class Node {public int val;public List children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List _children) {val = _val;children = _children;}};

LeetCode515（在每个树行中找最大值）

public class LeetCode515 { public List largestValues(TreeNode root) {List result = new LinkedList();Deque de = new LinkedList();if(root==null) {return result;}de.add(root);while(!de.isEmpty()) {int size = de.size();int max = Integer.MIN_VALUE;while(size-->0) {TreeNode temp = de.pollFirst();max = temp.val>max?temp.val:max;if(temp.left!=null) {de.addLast(temp.left);}if(temp.right!=null) {de.addLast(temp.right);}}result.add(max);}return result; }}

LeetCode116（填充每个节点的下一个右节点）

package tree;import java.util.Deque;import java.util.LinkedList;import java.util.List;public class LeetCode116 { public Node_116 connect(Node_116 root) {Deque de = new LinkedList();if(root==null){return root;}de.add(root);while(!de.isEmpty()) {int size = de.size();while(size-->0) {Node_116 temp = de.pollFirst();if(size!=0) {temp.next = de.peekFirst();}if(temp.left!=null) {de.addLast(temp.left);}if(temp.right!=null) {de.addLast(temp.right);}}}return root; }}class Node_116 {public int val;public Node_116 left;public Node_116 right;public Node_116 next;public Node_116() {}public Node_116(int _val) {val = _val;}public Node_116(int _val, Node_116 _left, Node_116 _right, Node_116 _next) {val = _val;left = _left;right = _right;next = _next;}};

LeetCode117（填充每个节点的下一个右节点II）同上

LeetCode104（二叉树的最大深度）

package tree;import java.util.Deque;import java.util.LinkedList;public class LeetCode104 {public int maxDepth(TreeNode root) {Deque de = new LinkedList();int len = 0;if(root==null) {return 0;}de.add(root);while(!de.isEmpty()) {int size = de.size();len++;while(size-->0) {TreeNode temp = de.pollFirst();if(temp.left!=null) {de.addLast(temp.left);}if(temp.right!=null) {de.addLast(temp.right);}}}return len;}}//递归class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}}

LeetCode111（二叉树的最小深度）

class Solution {public int minDepth(TreeNode root) {if(root==null){return 0;}if(root.left==null&&root.right==null){return 1;}int min_Depth = Integer.MAX_VALUE;if(root.left!=null){min_Depth = Math.min(minDepth(root.left),min_Depth);} if(root.right!=null){min_Depth = Math.min(minDepth(root.right),min_Depth);}return min_Depth+1;}}