X

LEETCODE 1469. Find All the Lonely Nodes 解题思路分析

题目大意:

找出所有单独节点

在一棵二叉树中,如果一个节点是他父节点唯一的子节点,那么该节点被称为单独节点。注意二叉树的根节点没有父节点,因此不属于单独节点。

给你一颗二叉树的根节点对象,请你返回二叉树中所有的单独节点。返回结果的顺序不限。

示例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-解题思路分析/
Categories: leetcode
kwantong: