Recently, I've reviewed several key topics related to data structures and algorithms, focusing on binary trees. This is the first article in a series that explores this fundamental structure. Let's start by defining the basic node structure of a binary tree:
class TreeNode { int val; // value of the node TreeNode left; // left child TreeNode right; // right child }
Binary tree problems are typically solved using either recursive or iterative approaches. Below are some common operations and algorithms implemented for binary trees:
1. **Finding the maximum depth of a binary tree**
int maxDepth(TreeNode node) { if (node == null) return 0; int left = maxDepth(node.left); int right = maxDepth(node.right); return Math.max(left, right) + 1; }
2. **Finding the minimum depth of a binary tree**
int getMinDepth(TreeNode root) { if (root == null) return 0; return getMin(root); } int getMin(TreeNode root) { if (root == null) return Integer.MAX_VALUE; if (root.left == null && root.right == null) return 1; return Math.min(getMin(root.left), getMin(root.right)) + 1; }
3. **Counting the number of nodes in a binary tree**
int countNodes(TreeNode root) { if (root == null) return 0; return countNodes(root.left) + countNodes(root.right) + 1; }
4. **Counting the number of leaf nodes in a binary tree**
int countLeafNodes(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) return 1; return countLeafNodes(root.left) + countLeafNodes(root.right); }
5. **Counting the number of nodes at the k-th level**
int countKLevelNodes(TreeNode root, int k) { if (root == null || k < 1) return 0; if (k == 1) return 1; return countKLevelNodes(root.left, k - 1) + countKLevelNodes(root.right, k - 1); }
6. **Checking if a binary tree is balanced**
boolean isBalanced(TreeNode node) { return maxDepth(node) != -1; } int maxDepth(TreeNode node) { if (node == null) return 0; int left = maxDepth(node.left); int right = maxDepth(node.right); if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1; return Math.max(left, right) + 1; }
7. **Checking if a binary tree is a complete binary tree**
A complete binary tree is one where all levels except possibly the last are completely filled, and all nodes are as far left as possible. Here's an implementation using a queue:
boolean isComplete(TreeNode root) { if (root == null) return false; Queue
8. **Checking if two binary trees are identical**
boolean areIdentical(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; return t1.val == t2.val && areIdentical(t1.left, t2.left) && areIdentical(t1.right, t2.right); }
9. **Checking if two binary trees are mirror images**
boolean areMirrors(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; return t1.val == t2.val && areMirrors(t1.left, t2.right) && areMirrors(t1.right, t2.left); }
10. **Flipping a binary tree (mirroring)**
TreeNode mirrorTree(TreeNode root) { if (root == null) return null; TreeNode left = mirrorTree(root.left); TreeNode right = mirrorTree(root.right); root.left = right; root.right = left; return root; }
11. **Finding the lowest common ancestor of two nodes**
TreeNode findLCA(TreeNode root, TreeNode t1, TreeNode t2) { if (contains(root.left, t1) && contains(root.right, t2)) return root; if (contains(root.left, t2) && contains(root.left, t1)) return findLCA(root.left, t1, t2); return findLCA(root.right, t1, t2); } boolean contains(TreeNode root, TreeNode node) { if (root == null) return false; if (root == node) return true; return contains(root.left, node) || contains(root.right, node); }
12. **Preorder traversal of a binary tree**
Iterative approach:
ArrayList
Recursive approach:
ArrayList
13. **In-order traversal of a binary tree**
ArrayList
14. **Post-order traversal of a binary tree**
ArrayList
15. **Constructing a binary tree from preorder and inorder traversals**
TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length != inorder.length) return null; return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { if (inStart > inEnd) return null; TreeNode root = new TreeNode(preorder[preStart]); int index = findIndex(inorder, inStart, inEnd, preorder[preStart]); root.left = build(preorder, preStart + 1, preStart + index - inStart, inorder, inStart, index - 1); root.right = build(preorder, preStart + index - inStart + 1, preEnd, inorder, index + 1, inEnd); return root; } int findIndex(int[] arr, int start, int end, int key) { for (int i = start; i <= end; i++) if (arr[i] == key) return i; return -1; }
16. **Inserting a node into a binary tree**
TreeNode insertNode(TreeNode root, TreeNode node) { if (root == null) return node; TreeNode current = root; TreeNode parent = null; while (current != null) { parent = current; if (current.val > node.val) current = current.left; else current = current.right; } if (parent.val > node.val) parent.left = node; else parent.right = node; return root; }
17. **Finding paths in a binary tree that sum to a given value**
void findPaths(TreeNode root, int target) { if (root == null) return; Stack
18. **Searching for values in a range in a binary search tree**
ArrayList
19. **Level order traversal of a binary tree**
ArrayList
20. **Finding the longest distance between any two nodes in a binary tree**
The longest path can be found through three cases: the sum of the depths of the left and right subtrees, or the longest path within the left or right subtree. Here’s a recursive solution:
private static class Result { int maxDistance; int maxDepth; public Result() {} public Result(int maxDistance, int maxDepth) { this.maxDistance = maxDistance; this.maxDepth = maxDepth; } } int getLongestDistance(TreeNode root) { return getLongestDistanceResult(root).maxDistance; } Result getLongestDistanceResult(TreeNode root) { if (root == null) return new Result(0, -1); Result left = getLongestDistanceResult(root.left); Result right = getLongestDistanceResult(root.right); Result result = new Result(); result.maxDepth = Math.max(left.maxDepth, right.maxDepth) + 1; result.maxDistance = Math.max(left.maxDepth + right.maxDepth, Math.max(left.maxDistance, right.maxDistance)); return result; }
21. **Counting different binary search trees**
Given n, how many unique BSTs can be formed? This is a classic dynamic programming problem:
int numTrees(int n) { int[] dp = new int[n + 2]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { for (int j = 0; j < i; j++) { dp[i] += dp[j] * dp[i - j - 1]; } } return dp[n]; }
22. **Checking if a binary tree is a valid binary search tree (BST)**
A BST must satisfy that every node’s left subtree contains only values less than the node, and the right subtree contains only values greater than the node. Here’s a method using in-order traversal:
int lastVal = Integer.MAX_VALUE; boolean firstNode = true; boolean isValidBST(TreeNode root) { if (root == null) return true; if (!isValidBST(root.left)) return false; if (!firstNode && lastVal >= root.val) return false; firstNode = false; lastVal = root.val; return isValidBST(root.right); }
These algorithms cover a wide range of binary tree operations and are commonly used in coding interviews. Understanding their logic and implementation will help you tackle similar problems with confidence.
Shenzhen ChengRong Technology Co.,Ltd. , https://www.laptopstandsupplier.com