94. Binary Tree Inorder Traversal Given the root of a binary tree, return the inorder traversal of its nodes’ values. Example 1: Input: root = [1,null,2,3] Output: [1,3,2] Example 2: Input: root = [] Output: [] Example 3: Input: root = [1] Output: [1] Example 4: Input: root = [1,2] Output: [2,1] Example 5: Input: root = [1,null,2] Output: [1,2] ...
144. Binary Tree Preorder Traversal Given the root of a binary tree, return the preorder traversal of its nodes’ values. Example 1: Input: root = [1,null,2,3] Output: [1,2,3] Example 2: Input: root = [] Output: [] Example 3: Input: root = [1] Output: [1] Example 4: Input: root = [1,2] Output: [1,2] Example 5: Input: root = [1,null,2] Output: [1,2] ...
149. Max Points on a Line Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line. Example 1: Input: points = [[1,1],[2,2],[3,3]] Output: 3 Example 2: Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Constraints: 1 <= points.length <= 300 points[i].length == 2 -104 <= xi, yi <= 104 All the points are unique. /** * 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 sortedArrayToBST(int[] nums) { if (nums.length == 0) return null; return buildBST(nums, 0, nums.length - 1); } TreeNode buildBST(int[] nums, int lo, int hi) { if (hi < lo) { return null; } TreeNode node = new TreeNode(); int mid = lo + (hi - lo) / 2; node.val = nums[mid]; node.left = buildBST(nums, lo, mid - 1); node.right = buildBST(nums, mid + 1, hi); return node; } }
108. Convert Sorted Array to Binary Search Tree Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one. Example 1: Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: [0,-10,5,null,-3,null,9] is also accepted: ...
110. Balanced Binary Tree Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of every node differ in height by no more than 1. Example 1: Input: root = [3,9,20,null,null,15,7] Output: true Example 2: Input: root = [1,2,2,3,3,null,null,4,4] Output: false Example 3: Input: root = [] Output: true Constraints: ...
111. Minimum Depth of Binary Tree 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. Example 1: Input: root = [3,9,20,null,null,15,7] Output: 2 Example 2: Input: root = [2,null,3,null,4,null,5,null,6] Output: 5 Constraints: The number of nodes in the tree is in the range [0, 105]. -1000 <= Node.val <= 1000 /** * 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 { int min = Integer.MAX_VALUE; public int minDepth(TreeNode root) { if (root == null) return 0; findMinDepth(root, 1); return min; } void findMinDepth(TreeNode node, int depth) { if (node == null) return; if (node.left == null && node.right == null) { min = Math.min(depth, min); } findMinDepth(node.left, depth + 1); findMinDepth(node.right, depth + 1); } } Solution 2021-08-23 /** * 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 { int min = Integer.MAX_VALUE; public int minDepth(TreeNode root) { findMinDepth(root, 1); return min == Integer.MAX_VALUE ? 0: min; } void findMinDepth(TreeNode node, int level) { if (node == null) { return; } if (node.left == null && node.right == null) { min = Math.min(min, level); return; } findMinDepth(node.left, level + 1); findMinDepth(node.right, level + 1); } } Solution with Stack 2021-11-11 /** * 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) { Stack<Pair<TreeNode, Integer>> stack = new Stack<>(); if (root == null) { return 0; } stack.push(new Pair<>(root, 1)); int min = Integer.MAX_VALUE; while (stack.size() > 0) { Pair<TreeNode, Integer> pair = stack.pop(); TreeNode node = pair.getKey(); Integer currentMin = pair.getValue(); if (node.left == null && node.right == null) { min = Math.min(min, currentMin); continue; } if (node.left != null) { stack.push(new Pair<>(node.left, currentMin + 1)); } if (node.right != null) { stack.push(new Pair<>(node.right, currentMin + 1)); } } return min; } }
![https://leetcode.com/problems/same-tree/] Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value. Example 1: Input: p = [1,2,3], q = [1,2,3] Output: true Example 2: Input: p = [1,2], q = [1,null,2] Output: false Example 3: Input: p = [1,2,1], q = [1,1,2] Output: false ...
!()[https://leetcode.com/problems/symmetric-tree/] Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Example 1: Input: root = [1,2,2,3,4,4,3] Output: true Example 2: Input: root = [1,2,2,null,3,null,3] Output: false Constraints: The number of nodes in the tree is in the range [1, 1000]. -100 <= Node.val <= 100 /** * 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 boolean isSymmetric(TreeNode root) { if (root == null) { return true; } List<TreeNode> q = new ArrayList<>(); q.add(root.left); q.add(root.right); while (q.size() > 1) { TreeNode left = q.remove(0); TreeNode right = q.remove(0); if (left == null && left == right) { continue; } if (left == null || right == null) { return false; } if (left.val != right.val) { return false; } q.add(left.left); q.add(right.right); q.add(left.right); q.add(right.left); } return true; } public boolean isSymmetricRecursive(TreeNode root) { if (root == null) { return true; } return isSymmetric(root.left, root.right); } boolean isSymmetric(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 isSymmetric(left.left, right.right) && isSymmetric(right.left, left.right); } }
104. Maximum Depth of Binary Tree 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. Example 1: Input: root = [3,9,20,null,null,15,7] Output: 3 Example 2: Input: root = [1,null,2] Output: 2 Example 3: Input: root = [] Output: 0 Example 4: Input: root = [0] Output: 1 Constraints: ...
112. Path Sum 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. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Example 3: Input: root = [1,2], targetSum = 0 Output: false Constraints: ...