本文共 1800 字，大约阅读时间需要 6 分钟。

In a binary tree, a lonely node is a node that is the only child of its parent node. The root of the tree is not lonely because it does not have a parent node.

Given the root of a binary tree, return an array containing the values of all lonely nodes in the tree. Return the list in any order.

Example 1:

Input: root = [1,2,3,null,4]Output: [4]Explanation: Light blue node is the only lonely node.Node 1 is the root and is not lonely.Nodes 2 and 3 have the same parent and are not lonely.

Example 2:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]Output: [6,2]Explanation: Light blue nodes are lonely nodes.Please remember that order doesn't matter, [2,6] is also an acceptable answer.

Example 3:

Input: root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22]Output: [77,55,33,66,44,22]Explanation: Nodes 99 and 88 share the same parent. Node 11 is the root.All other nodes are lonely.

Example 4:

Input: root = [197]Output: []

Example 5:

Input: root = [31,null,78,null,28]Output: [78,28]

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Each node's value is between [1, 10^6].

题意：给定一棵二叉树的根节点 root ，返回树中 所有的独生节点的值所构成的数组 。数组的顺序 不限 。

解法 DFS

使用DFS，当前节点根据传递下来的信息（这一节点是否是独生节点），决定节点值是否加入结果；然后判断当前节点的左右子节点是否是独生节点，递归调用并传递信息：

class Solution {
   private:    vector
   
     ans;    void dfs(TreeNode* root, bool isLone) {
           if (root == nullptr) return;        if (isLone) ans.push_back(root->val); //是独生节点        bool flag = (root->left && !root->right) || (!root->left && root->right);        dfs(root->left, flag);        dfs(root->right, flag);    }public:    vector
    
      getLonelyNodes(TreeNode* root) {
           dfs(root, false);        return ans;    }};
    
   

运行效率如下：

执行用时：24 ms, 在所有 C++ 提交中击败了81.15% 的用户内存消耗：20.4 MB, 在所有 C++ 提交中击败了30.58% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/111404752 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！