Time:O(n) Space:O(h) C++ class Solution { public: vector<int> getLonelyNodes(TreeNode* root) { vector<int> ans; dfs(root, false, ans); return ans; } private: void dfs(TreeNode* root, bool isLonely, vector<int>& ans) { if (!root) return; if (isLonely) ans.push_back(root->val); dfs(root->left, !root->right, ans); dfs(root->right, !root->left, ans); } }; JAVA class Solution { public List<Integer> getLonelyNodes(TreeNode root) { List<Integer> ans = new ArrayList<>(); dfs(root, false, ans); return ans; } private void dfs(TreeNode root, boolean isLonely, List<Integer> ans) { if (root == null) return; if (isLonely) ans.add(root.val); dfs(root.left, root.right == null, ans); dfs(root.right, root.left == null, ans); } }