1469. Find All The Lonely Nodes

 一刷 07/2022

Version #1 DFS

一开始完全写错以为lonely node就是左右子树都空的node，大错特错

所以做题还是要看清题意

Time O(N)

Space O(h) - height of the tree, could be O(N) in the worst case

Runtime: 1 ms, faster than 89.99% of Java online submissions for Find All The Lonely Nodes.

Memory Usage: 46.1 MB, less than 76.86% of Java online submissions for Find All The Lonely Nodes.

class Solution {

    public List<Integer> getLonelyNodes(TreeNode root) {

        if (root == null) {

            return new ArrayList<>();

        }

        List<Integer> result = new ArrayList<>();

        findNodeDFS(root, result, false);

        return result;

    }

    

    private void findNodeDFS(TreeNode node, List<Integer> result, boolean isLonely) {

        if (node == null) {

            return;

        }

        if (isLonely) {

            result.add(node.val);

        }

        if (node.left != null && node.right != null) {

            findNodeDFS(node.left, result, false);

            findNodeDFS(node.right, result, false);

            return;

        }

        findNodeDFS(node.left, result, true);

        findNodeDFS(node.right, result, true);

    }

}