题目大意：
找出所有单独节点
在一棵二叉树中，如果一个节点是他父节点唯一的子节点，那么该节点被称为单独节点。注意二叉树的根节点没有父节点，因此不属于单独节点。
给你一颗二叉树的根节点对象，请你返回二叉树中所有的单独节点。返回结果的顺序不限。
示例1：
输入: root = [1,2,3,null,4] 输出: [4] 解释: 浅蓝色的节点是本例中唯一的一个单独节点. 节点1是根节点因此它不是单独节点. 节点2和3拥有同一个父节点，因此他们不是单独节点.
示例2：
输入: root = [7,1,4,6,null,5,3,null,null,null,null,null,2] 输出: [6,2] 解释: 浅蓝色的节点都是单独节点. 请记住返回结果的顺序无所谓, [2,6] 也是一个正确答案.
示例3：
输入: root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22] 输出: [77,55,33,66,44,22] 解释: 节点99和88拥有同一个父节点. 节点11是根节点. 其他节点都是单独节点.
示例4:
输入: root = [197] 输出: []
示例5:
输入: root = [31,null,78,null,28] 输出: [78,28]
提示:
- 二叉树节点数量在
[1, 1000] 范围内. - 每个节点的数值在
[1, 10^6] 范围内.
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1469
解题思路分析：
简单的二叉树问题。我们之前的文章多次提到过，解决二叉树问题的最佳方案就是dfs深度优先搜索，本题也不例外。我们从根节点开始向下做dfs递归操作。如果当前节点的左子节点不为空并且右子节点为空，那么左子节点是一个单独节点。另外如果左子节点为空并且右子节点不为空，那么右子节点是一个单独节点。接下来，我们再dfs递归至左子节点和右子节点，继续重复上述逻辑直到遍历完所有节点为止。
实现代码：
List<Integer> res=new ArrayList<>(); // 返回结果
public List<Integer> getLonelyNodes(TreeNode root) {
dfs(root); // dfs每个节点
return res;
}
void dfs(TreeNode root){
// 如果左子节点不为空并且右子节点为空
if(root.left!=null&&root.right==null){
// 左子节点是一个单独节点
res.add(root.left.val);
}
// 如果左子节点不空并且右子节点不为空
if(root.left==null&&root.right!=null){
// 右子节点是一个单独节点
res.add(root.right.val);
}
if(root.left!=null) dfs(root.left); // dfs至左子节点
if(root.right!=null) dfs(root.right); // dfs至右子节点
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Find All the Lonely Nodes.
Memory Usage: 40.5 MB, less than 100.00% of Java online submissions for Find All the Lonely Nodes.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1469-find-all-the-lonely-nodes-解题思路分析/