144,94,145
102,107,199,515,116,104,111,226,101
104,559,111,222
110,257,404
513,112,113,106,105
144. Binary Tree Preorder Traversal
Easy
Given the root of a binary tree, return the preorder traversal of its nodes' values.
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList();
if(root == null){
return ans;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode pop = stack.pop();
ans.add(pop.val);
if(pop.right != null){
stack.push(pop.right);
}
if(pop.left != null){
stack.push(pop.left);
}
}
return ans;
}
}
class Solution {
List<Integer> ans = new ArrayList();
public List<Integer> preorderTraversal(TreeNode root) {
preorder(root);
return ans;
}
private void preorder(TreeNode root){
if(root == null){
return;
}
ans.add(root.val);
preorder(root.left);
preorder(root.right);
}
}94. Binary Tree Inorder Traversal
Easy
Given the root of a binary tree, return the inorder traversal of its nodes' values.
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if(root == null){
return ans;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
ans.add(cur.val);
cur = cur.right;
}
}
return ans;
}
}class Solution {
List<Integer> ans = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
inorder(root);
return ans;
}
private void inorder(TreeNode root){
if(root == null){
return;
}
inorder(root.left);
ans.add(root.val);
inorder(root.right);
}
}145. Binary Tree Postorder Traversal
Easy
Given the root of a binary tree, return the postorder traversal of its nodes' values.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if(root == null){
return ans;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
TreeNode pop = null;
while(cur != null || !stack.isEmpty()){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
TreeNode peek = stack.peek();
if(peek.right == null){
pop = stack.pop();
ans.add(pop.val);
}else if(peek.right == pop){
pop = stack.pop();
ans.add(pop.val);
}else{
cur = peek.right;
}
}
}
return ans;
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
postorder(root, ans);
return ans;
}
private void postorder(TreeNode root, List<Integer> ans) {
if (root == null) {
return;
}
postorder(root.left, ans);
postorder(root.right, ans);
ans.add(root.val);
}
}102. Binary Tree Level Order Traversal
Medium
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if(root == null){
return ans;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int n = queue.size();
List<Integer> levelList = new ArrayList<>();
while(n > 0){
TreeNode poll = queue.poll();
levelList.add(poll.val);
if(poll.left != null){
queue.offer(poll.left);
}
if(poll.right != null){
queue.offer(poll.right);
}
n--;
}
ans.add(levelList);
}
return ans;
}
}199. Binary Tree Right Side View
Medium
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) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int n = queue.size();
while (n > 0) {
TreeNode poll = queue.poll();
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
if (n == 1) {
ans.add(poll.val);
}
n--;
}
}
return ans;
}
}515. Find Largest Value in Each Tree Row
Medium
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) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> que = new LinkedList();
que.offer(root);
while (!que.isEmpty()){
int n = que.size();
int max = Integer.MIN_VALUE;
while (n>0){
TreeNode poll = que.poll();
max = Math.max(max,poll.val);
if(poll.left!=null) que.offer(poll.left);
if(poll.right!=null) que.offer(poll.right);
n--;
}
ans.add(max);
}
return ans;
}
}116. Populating Next Right Pointers in Each Node
Medium
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
class Solution {
public Node connect(Node root) {
Queue<Node> queue = new LinkedList<>();
if(root==null)return root;
queue.add(root);
while(queue.size()!=0){
int n = queue.size();
while(n>0){
Node node = queue.poll();
if(node.left!=null)queue.add(node.left);
if(node.right!=null)queue.add(node.right);
n--;
if(n>0)node.next = queue.peek();
}
}
return root;
}
}
class Solution {
public Node connect(Node root) {
if(root==null){
return null;
}
Node leftmost=root;
while(leftmost.left!=null){
Node current=leftmost;
while(current!=null){
current.left.next=current.right;
if(current.next!=null){
current.right.next=current.next.left;
}
current=current.next;
}
leftmost=leftmost.left;
}
return root;
}
}104. Maximum Depth of Binary Tree
Easy
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth , rightDepth) + 1;
}
}class Solution {
public int maxDepth(TreeNode root) {
int ans = 0;
if(root==null){
return ans;
}
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while(!queue.isEmpty()){
int n = queue.size();
while(n>0){
TreeNode poll = queue.poll();
if(poll.left!=null){
queue.offer(poll.left);
}
if(poll.right!=null){
queue.offer(poll.right);
}
n--;
}
ans++;
}
return ans;
}
}Easy
Given the root of a binary tree, invert the tree, and return its root.
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
root.left = invertTree(root.left);
root.right = invertTree(root.right);
return root;
}
}
Easy
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
class Solution {
public boolean isSymmetric(TreeNode root) {
return compare(root.left, root.right);
}
private boolean compare(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return compare(left.right, right.left) && compare(left.left, right.right);
}
}
class Solution {
public boolean isSymmetric(TreeNode root) {
Deque<TreeNode> queue = new LinkedList<>();//ArrayDeque不能放null
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode leftNode = queue.poll();
TreeNode rightNode = queue.poll();
if (leftNode == null && rightNode == null) {
continue;//LinkedList里有null这个元素也会被认为非空
}
if (leftNode == null || rightNode == null || rightNode.val != leftNode.val) {
return false;
}
queue.offer(leftNode.left);
queue.offer(rightNode.right);
queue.offer(leftNode.right);
queue.offer(rightNode.left);
}
return true;
}
}222. Count Complete Tree Nodes
Easy
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
559. Maximum Depth of N-ary Tree
Easy
Given a n-ary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
class Solution {
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
int maxDepth = 0;
for (Node node : root.children) {
maxDepth = Math.max(maxDepth, maxDepth(node));
}
return maxDepth + 1;
}
}
Easy
Given a binary tree, determine if it is
height-balanced
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
public int getHeight(TreeNode root) {//可以按照例子自己推一推
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = getHeight(root.right);
if (rightHeight == -1) {
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
}.
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null). return true;
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 &&
isBalanced(root.left) &&
isBalanced(root.right);
}
private int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}Easy
Given the root of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.
class Solution {
List<String> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(root);
return ans;
}
private void dfs(TreeNode root){
if(root == null){
return;
}
path.add(root.val);
if(root.left == null && root.right ==null){
StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
for (int i = 0; i < path.size() - 1; i++) {
sb.append(path.get(i)).append("->");
}
sb.append(path.get(path.size() - 1));// 记录最后一个节点
ans.add(sb.toString());// 收集一个路径
}
dfs(root.left);
dfs(root.right);
path.remove(path.size()-1);
}
}class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();// 存最终的结果
if (root == null) {
return res;
}
List<Integer> paths = new ArrayList<>();// 作为结果中的路径
traversal(root, paths, res);
return res;
}
private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
paths.add(root.val);// 前序遍历，中
// 遇到叶子结点
if (root.left == null && root.right == null) {
// 输出
StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
for (int i = 0; i < paths.size() - 1; i++) {
sb.append(paths.get(i)).append("->");
}
sb.append(paths.get(paths.size() - 1));// 记录最后一个节点
res.add(sb.toString());// 收集一个路径
return;
}
// 递归和回溯是同时进行，所以要放在同一个花括号里
if (root.left != null) { // 左
traversal(root.left, paths, res);
paths.remove(paths.size() - 1);// 回溯
}
if (root.right != null) { // 右
traversal(root.right, paths, res);
paths.remove(paths.size() - 1);// 回溯
}
}
}Easy
Given the root of a binary tree, return the sum of all left leaves.
A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
int sum = 0;
if(root == null){
return 0;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode pop = stack.pop();
if(pop.right != null){
stack.push(pop.right);
}
if(pop.left != null){
if(pop.left.left == null && pop.left.right == null){
sum += pop.left.val;
}
stack.push(pop.left);
}
}
return sum;
}
}class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null){
return 0;
}
int sum = 0;
if(root.left != null && root.left.left == null && root.left.right == null){
sum += root.left.val;
}
sum += sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
return sum;
}
}513. Find Bottom Left Tree Value
Solved
Medium
Topics
Companies
Given the root of a binary tree, return the leftmost value in the last row of the tree.
class Solution {
int maxDepth = 0;
int ans;
public int findBottomLeftValue(TreeNode root) {
ans = root.val;
dfs(root , 1);
return ans;
}
private void dfs(TreeNode root, int depth){
if(root == null){
return;
}
if(root.left == null && root.right == null && depth > maxDepth){
ans = root.val;
maxDepth = depth;
}
dfs(root.left , depth +1);
dfs(root.right , depth +1);
}
}class Solution {
public int findBottomLeftValue(TreeNode root) {
Deque<TreeNode> queue = new LinkedList<>();
int ans = root.val;
queue.offer(root);
while(!queue.isEmpty()){
int n = queue.size();
int size = queue.size();
while(n > 0){
TreeNode poll = queue.poll();
if(n == size){
ans = poll.val;
}
if(poll.left != null){
queue.offer(poll.left);
}
if(poll.right != null){
queue.offer(poll.right);
}
n--;
}
}
return ans;
}
}Easy
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null){
return false;
}
if(root.left == null && root.right == null){
return root.val == targetSum;
}
boolean left = false;
boolean right = false;
if(root.left != null){
left = hasPathSum(root.left , targetSum - root.val);
}
if(root.right != null){
right = hasPathSum(root.right , targetSum - root.val);
}
return left || right;
}
}
Medium
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root == null){
return ans;
}
dfs(root, targetSum);
return ans;
}
private void dfs(TreeNode root , int targetSum){
path.add(root.val);
if(root.left == null && root.right == null){
if(root.val == targetSum){
ans.add(new ArrayList(path));
}
}
if(root.left != null){
dfs(root.left , targetSum - root.val);
path.remove(path.size()-1);
}
if(root.right != null){
dfs(root.right , targetSum - root.val);
path.remove(path.size()-1);
}
}
}
105. Construct Binary Tree from Preorder and Inorder Traversal
Medium
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
}
int rootValue = preorder[0];
TreeNode root = new TreeNode(rootValue);
int middleIndex = -1;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootValue) {
middleIndex = i;
break;
}
}
int[] leftInorder = Arrays.copyOfRange(inorder, 0, middleIndex);//copyOfRange包前不包后
int[] rightInorder = Arrays.copyOfRange(inorder, middleIndex + 1, inorder.length);
int[] leftPreorder = Arrays.copyOfRange(preorder, 1, middleIndex + 1);
int[] rightPreorder = Arrays.copyOfRange(preorder, middleIndex + 1, preorder.length);
root.left = buildTree(leftPreorder, leftInorder);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
}
class Solution {
Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
map.put(inorder[i], i);
}
return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length); // 前闭后开
}
public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
// 参数里的范围都是前闭后开
if (preBegin >= preEnd || inBegin >= inEnd) { // 不满足左闭右开，说明没有元素，返回空树
return null;
}
int rootIndex = map.get(preorder[preBegin]); // 找到前序遍历的第一个元素在中序遍历中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定前序数列的个数
root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
inorder, inBegin, rootIndex);
root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
inorder, rootIndex + 1, inEnd);
return root;
}
}106. Construct Binary Tree from Inorder and Postorder Traversal
Medium
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
class Solution {
Map<Integer, Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return buildHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
private TreeNode buildHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return null;
}
int rootValue = postorder[postEnd];
TreeNode root = new TreeNode(rootValue);
int rootIndex = map.get(rootValue);
int leftSize = rootIndex - inStart;
root.left = buildHelper(inorder, inStart, rootIndex - 1,
postorder, postStart, postStart + leftSize - 1);
root.right = buildHelper(inorder, rootIndex + 1, inorder.length - 1,
postorder, postStart + leftSize, postEnd - 1);
return root;
}
}
