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: ...
113. Path Sum II Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path’s sum 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,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]] Example 2: Input: root = [1,2,3], targetSum = 5 Output: [] Example 3: Input: root = [1,2], targetSum = 0 Output: [] Constraints: ...