Untitled
unknown
plain_text
2 months ago
4.9 kB
2
Indexable
Here’s the recursive implementation of the `addLeftBoundary` method to match the recursive style used for `addRightBoundary`. ### Recursive `addLeftBoundary`: ```java private void addLeftBoundary(TreeNode node, List<Integer> result) { if (node == null || isLeaf(node)) { return; } // Add the current node before processing its children result.add(node.val); // Recur for the left child first, then for the right child if left is absent if (node.left != null) { addLeftBoundary(node.left, result); } else { addLeftBoundary(node.right, result); } } ``` --- ### Updated Full Example: Here’s the complete `BoundaryTraversal` class with both `addLeftBoundary` and `addRightBoundary` implemented recursively: ```java import java.util.ArrayList; import java.util.List; class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; left = right = null; } } public class BoundaryTraversal { public List<Integer> boundaryTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; // Add root value (not a leaf) if (!isLeaf(root)) result.add(root.val); // Traverse the left boundary addLeftBoundary(root.left, result); // Traverse the leaf nodes addLeaves(root, result); // Traverse the right boundary addRightBoundary(root.right, result); return result; } private void addLeftBoundary(TreeNode node, List<Integer> result) { if (node == null || isLeaf(node)) { return; } // Add the current node before processing its children result.add(node.val); // Recur for the left child first, then for the right child if left is absent if (node.left != null) { addLeftBoundary(node.left, result); } else { addLeftBoundary(node.right, result); } } private void addLeaves(TreeNode node, List<Integer> result) { if (node == null) return; if (isLeaf(node)) { result.add(node.val); return; } addLeaves(node.left, result); addLeaves(node.right, result); } private void addRightBoundary(TreeNode node, List<Integer> result) { if (node == null || isLeaf(node)) { return; } // Recur for the right child first, then for the left child if right is absent if (node.right != null) { addRightBoundary(node.right, result); } else { addRightBoundary(node.left, result); } // Add the current node after processing its children result.add(node.val); } private boolean isLeaf(TreeNode node) { return node.left == null && node.right == null; } public static void main(String[] args) { // Example Tree TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); root.right.right = new TreeNode(7); root.left.right.left = new TreeNode(8); root.left.right.right = new TreeNode(9); root.right.right.left = new TreeNode(10); root.right.right.right = new TreeNode(11); BoundaryTraversal bt = new BoundaryTraversal(); List<Integer> boundary = bt.boundaryTraversal(root); System.out.println(boundary); // Output: [1, 2, 4, 8, 9, 10, 11, 7, 3] } } ``` --- ### Explanation of Recursive `addLeftBoundary`: 1. **Base Condition**: - The recursion stops when the current node is `null` or a leaf node. 2. **Action on Current Node**: - Add the current node to the `result` list since it is part of the left boundary. 3. **Recursive Call**: - Recur on the left child if it exists; otherwise, recur on the right child. This ensures the boundary traversal always follows the leftmost path. --- ### Output for Example Tree: Input Tree: ``` 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / \ 8 9 10 11 ``` **Boundary Traversal**: - Left Boundary: \( [1, 2, 4] \) - Leaf Nodes: \( [8, 9, 6, 10, 11] \) - Right Boundary: \( [3, 7] \) (in reverse order) **Output**: \( [1, 2, 4, 8, 9, 6, 10, 11, 7, 3] \) --- ### Complexity: 1. **Time Complexity**: - \( O(n) \): Each node is visited exactly once. 2. **Space Complexity**: - \( O(h) \): Recursion stack space, where \( h \) is the height of the tree.
Editor is loading...
Leave a Comment