package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 545. Boundary of Binary Tree
 *
 * Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root.
 * Boundary includes left boundary, addLeaves, and right boundary in order without duplicate nodes.
 * Left boundary is defined as the path from root to the left-most node.
 * Right boundary is defined as the path from root to the right-most node.
 * If the root doesn't have left subtree or right subtree,
 * then the root itself is left boundary or right boundary.
 * Note this definition only applies to the input binary tree, and not applies to any subtrees.
 * The left-most node is defined as a leaf node you could reach when you always firstly travel
 * to the left subtree if exists. If not, travel to the right subtree.
 * Repeat until you reach a leaf node.
 * The right-most node is also defined by the same way with left and right exchanged.

 Example 1
 Input:
  1
   \
   2
  / \
 3   4

 Ouput:
 [1, 3, 4, 2]

 Explanation:
 The root doesn't have left subtree, so the root itself is left boundary.
 The addLeaves are node 3 and 4.
 The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
 So order them in anti-clockwise without duplicates and we have [1,3,4,2].


 Example 2
 Input:
    ____1_____
   /          \
  2           3
 / \          /
4   5        6
   / \      / \
  7  8     9  10

 Ouput:
 [1,2,4,7,8,9,10,6,3]

 Explanation:
 The left boundary are node 1,2,4. (4 is the left-most node according to definition)
 The addLeaves are node 4,7,8,9,10.
 The right boundary are node 1,3,6,10. (10 is the right-most node).
 So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

 */
public class _545 {
    public static class Solution1 {
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            List<Integer> nodes = new ArrayList<>();
            if (root == null) {
                return nodes;
            }

            nodes.add(root.val);
            leftBoundary(root.left, nodes);
            addLeaves(root.left, nodes);
            addLeaves(root.right, nodes);
            rightBoundary(root.right, nodes);
            return nodes;
        }

        public void leftBoundary(TreeNode root, List<Integer> nodes) {
            if (root == null || (root.left == null && root.right == null)) {
                /**we don't want to add any LEAVES in leftBoundary and rightBoundary functions either,
                 * that's why we have the later condition in the if branch.*/
                return;
            }
            nodes.add(root.val);// add BEFORE child visit
            if (root.left == null) {
                leftBoundary(root.right, nodes);
            } else {
                leftBoundary(root.left, nodes);
            }
        }

        public void rightBoundary(TreeNode root, List<Integer> nodes) {
            if (root == null || (root.right == null && root.left == null)) {
                return;
            }
            if (root.right == null) {
                rightBoundary(root.left, nodes);
            } else {
                rightBoundary(root.right, nodes);
            }
            nodes.add(root.val); // add AFTER child visit(reverse)
        }

        public void addLeaves(TreeNode root, List<Integer> nodes) {
            if (root == null) {
                return;
            }
            if (root.left == null && root.right == null) {
                nodes.add(root.val);
                return;
            }
            addLeaves(root.left, nodes);
            addLeaves(root.right, nodes);
        }
    }

}

@@ -134,1752 +134,8 @@
 t;%0A%0A
-/**%0A * 545. Boundary of Binary Tree%0A *%0A * Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root.%0A * Boundary includes left boundary, addLeaves, and right boundary in order without duplicate nodes.%0A * Left boundary is defined as the path from root to the left-most node.%0A * Right boundary is defined as the path from root to the right-most node.%0A * If the root doesn't have left subtree or right subtree,%0A * then the root itself is left boundary or right boundary.%0A * Note this definition only applies to the input binary tree, and not applies to any subtrees.%0A * The left-most node is defined as a leaf node you could reach when you always firstly travel%0A * to the left subtree if exists. If not, travel to the right subtree.%0A * Repeat until you reach a leaf node.%0A * The right-most node is also defined by the same way with left and right exchanged.%0A%0A Example 1%0A Input:%0A  1%0A   %5C%0A   2%0A  / %5C%0A 3   4%0A%0A Ouput:%0A %5B1, 3, 4, 2%5D%0A%0A Explanation:%0A The root doesn't have left subtree, so the root itself is left boundary.%0A The addLeaves are node 3 and 4.%0A The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.%0A So order them in anti-clockwise without duplicates and we have %5B1,3,4,2%5D.%0A%0A%0A Example 2%0A Input:%0A    ____1_____%0A   /          %5C%0A  2           3%0A / %5C          /%0A4   5        6%0A   / %5C      / %5C%0A  7  8     9  10%0A%0A Ouput:%0A %5B1,2,4,7,8,9,10,6,3%5D%0A%0A Explanation:%0A The left boundary are node 1,2,4. (4 is the left-most node according to definition)%0A The addLeaves are node 4,7,8,9,10.%0A The right boundary are node 1,3,6,10. (10 is the right-most node).%0A So order them in anti-clockwise without duplicate nodes we have %5B1,2,4,7,8,9,10,6,3%5D.%0A%0A */%0A
 publ

refactor 545