1469. Find All The Lonely Nodes

leetcode easy

#array#csharp#easy#graph#leetcode#recursion#search#tree#two-pointers

Task

В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.

Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке.

Пример:

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.

C# solution

matched/original

using System;
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public void DFS(TreeNode root, bool isLonely, List<int> 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);
    }
    
    public IList<int> GetLonelyNodes(TreeNode root) {
        List<int> ans = new List<int>();
        DFS(root, false, ans);
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    public void DFS(TreeNode root, bool isLonely, List<int> ans) {
        if (root == null) {
            return;
        }
        
        if (isLonely) {
            ans.push_back(root.val);
        }
        
        DFS(root.left, root.right == null, ans);
        DFS(root.right, root.left == null, ans);
    }
    
    public vector<int> GetLonelyNodes(TreeNode root) {
        List<int> ans = new List<int>();
        DFS(root, false, ans);
        return ans;
    }
}

Java solution

matched/original

class Solution {
    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);
    }
    
    public List<Integer> getLonelyNodes(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        DFS(root, false, ans);

        return ans;
    }
}

JavaScript solution

matched/original

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var DFS = function(root, isLonely, ans) {
    if (root === null) {
        return;
    }
    
    if (isLonely) {
        ans.push(root.val);
    }
    
    DFS(root.left, root.right === null, ans);
    DFS(root.right, root.left === null, ans);
};

var getLonelyNodes = function(root) {
    const ans = [];
    DFS(root, false, ans);
    return ans;
};

Python solution

matched/original

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def DFS(self, root, isLonely, ans):
        if root is None:
            return
        
        if isLonely:
            ans.append(root.val)
        
        self.DFS(root.left, root.right is None, ans)
        self.DFS(root.right, root.left is None, ans)
    
    def getLonelyNodes(self, root):
        ans = []
        self.DFS(root, False, ans)
        return ans

Go solution

matched/original

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func DFS(root *TreeNode, isLonely bool, ans *[]int) {
    if root == nil {
        return
    }
    
    if isLonely {
        *ans = append(*ans, root.Val)
    }
    
    DFS(root.Left, root.Right == nil, ans)
    DFS(root.Right, root.Left == nil, ans)
}

func getLonelyNodes(root *TreeNode) []int {
    var ans []int
    DFS(root, false, &ans)
    return ans
}

func main() {
    // Example usage:
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Right = &TreeNode{Val: 4}
    
    fmt.Println(getLonelyNodes(root)) // Output: [4]
}

Explanation

Algorithm

1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.

2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.

3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.

😎