LeetCode : 545. Boundary of Binary Tree

[congr]

https://leetcode.com/problems/boundary-of-binary-tree/

[congr]

Understanding the description was very tricky.

[congr]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> list = new ArrayList();
        if (root == null) return list;

        list.add(root.val);             // root
        getLeftSide(root.left, list);   // left boundary
        getLeaf(root, list);            // leaves
        getRightSide(root.right, list); // right boundary

        return list;
    }

    void getLeaf(TreeNode root, List<Integer> list) {
        if (root == null) return;

        Stack<TreeNode> st = new Stack();
        st.add(root);
        while (!st.isEmpty()) {
            TreeNode node = st.pop();
            if (node != root && node.left == null && node.right == null)
                list.add(node.val);

            if (node.right != null) st.push(node.right);
            if (node.left != null) st.push(node.left);
        }    
    }

    void getLeftSide(TreeNode root, List<Integer> list) {
        while (root != null) {
            if (root.left == null && root.right == null); // leaves
            else list.add(root.val);
            if (root.left == null) root = root.right;
            else root = root.left;
        }
    }

    void getRightSide(TreeNode root, List<Integer> list) {
        if (root == null) return;

        Stack<Integer> st = new Stack();
        while (root != null) {
            if (root.left == null && root.right == null); // leaves
            else st.push(root.val);
            if (root.right == null) root = root.left;
            else root = root.right;
        }        

        while (!st.isEmpty()) list.add(st.pop());
    }
}

[congr]

The method to get Leaves is different, but recursion makes shorter.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> nodes = new ArrayList<>();
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {

        if(root == null) return nodes;

        nodes.add(root.val);
        leftBoundary(root.left);
        leaves(root.left);
        leaves(root.right);
        rightBoundary(root.right);

        return nodes;
    }
    public void leftBoundary(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return;
        nodes.add(root.val);
        if(root.left == null) leftBoundary(root.right);
        else leftBoundary(root.left);
    }
    public void rightBoundary(TreeNode root) {
        if(root == null || (root.right == null && root.left == null)) return;
        if(root.right == null)rightBoundary(root.left);
        else rightBoundary(root.right);
        nodes.add(root.val); // add after child visit(reverse)
    }
    public void leaves(TreeNode root) {
        if(root == null) return;
        if(root.left == null && root.right == null) {
            nodes.add(root.val);
            return;
        }
        leaves(root.left);
        leaves(root.right);
    }
}