Leetcode

Find All The Lonely Nodes

May 26, 2022 by aAshish

  • 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);
  }
}