LeetCode 545: Boundary of Binary Tree
Problem Description
Explanation:
The problem "Boundary of Binary Tree" asks us to return the boundary of a binary tree in anti-clockwise order starting from the root. The boundary of a binary tree consists of four parts: the left boundary, the leaves, the right boundary, and the root.
To solve this problem, we can follow these steps:
- Traverse the left boundary in a top-down manner until we reach the leftmost leaf node.
- Traverse the leaf nodes from left to right.
- Traverse the right boundary in a bottom-up manner starting from the rightmost leaf node.
- Construct the boundary by combining these three parts.
Time Complexity: O(n) where n is the number of nodes in the binary tree. Space Complexity: O(n) for the recursive function calls and the output boundary list.
:
Solutions
class Solution {
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
List<Integer> boundary = new ArrayList<>();
if (root == null) {
return boundary;
}
boundary.add(root.val);
if (root.left != null) {
getLeftBoundary(root.left, boundary);
}
getLeaves(root, boundary);
if (root.right != null) {
getRightBoundary(root.right, boundary);
}
return boundary;
}
private void getLeftBoundary(TreeNode node, List<Integer> boundary) {
if (node == null || (node.left == null && node.right == null)) {
return;
}
boundary.add(node.val);
if (node.left == null) {
getLeftBoundary(node.right, boundary);
} else {
getLeftBoundary(node.left, boundary);
}
}
private void getLeaves(TreeNode node, List<Integer> boundary) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
boundary.add(node.val);
}
getLeaves(node.left, boundary);
getLeaves(node.right, boundary);
}
private void getRightBoundary(TreeNode node, List<Integer> boundary) {
if (node == null || (node.left == null && node.right == null)) {
return;
}
if (node.right == null) {
getRightBoundary(node.left, boundary);
} else {
getRightBoundary(node.right, boundary);
}
boundary.add(node.val);
}
}Related LeetCode Problems
Loading editor...