python3 解法, 执行用时: 56 ms, 内存消耗: 17.6 MB, 提交时间: 2023-10-15 18:22:59

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getLonelyNodes(self, root: TreeNode) -> List[int]:
        
        res = []

        def dfs(root: TreeNode) -> None:
            if root.left and root.right:        #2个孩子
                dfs(root.left)
                dfs(root.right)
            elif root.left and root.right==None:    #只有左子
                res.append(root.left.val)
                dfs(root.left)
            elif root.right and root.left==None:    #只有右子
                res.append(root.right.val)
                dfs(root.right)
            else:                                   #没有孩子
                return 
        
        dfs(root)
        return res
        
    # bfs
    def getLonelyNodes2(self, root: TreeNode) -> List[int]:
        que = [root]
        res = []
        while que:
            cur_len = len(que)
            for _ in range(cur_len):
                cur = que.pop(0)
                if cur.left:                #有左子
                    que.append(cur.left)
                    if cur.right:           #有右子
                        que.append(cur.right)
                    else:                   #无右子 左子是独子
                        res.append(cur.left.val)
                else:                       #无左子
                    if cur.right:           #有右子  右子是独子
                        que.append(cur.right)
                        res.append(cur.right.val)
        return res

java 解法, 执行用时: 3 ms, 内存消耗: 43.2 MB, 提交时间: 2023-10-15 18:22:07

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> getLonelyNodes(TreeNode root) {

        List<Integer> ans = new ArrayList<>();
        if(root == null || (root.left == null && root.right == null)) {
            return ans;
        }

        if(root.left != null && root.right == null) {
            ans.add(root.left.val);
        } 
        if(root.right != null && root.left == null) {
            ans.add(root.right.val);
        }

        List<Integer> l = getLonelyNodes(root.left);
        List<Integer> r = getLonelyNodes(root.right);

        ans.addAll(l);
        ans.addAll(r);

        return ans;

    }
}

golang 解法, 执行用时: 4 ms, 内存消耗: 7.4 MB, 提交时间: 2023-10-15 18:21:37

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import (
	"fmt"
)

func preProcess(array []int)[]int{
	for i:=0;i<len(array);i++{
		if array[i] == 0{
			pos := 2*i+1
			if pos >= len(array){break}
			back := append([]int{},array[pos:]...)
			array = append(array[:pos],[]int{0,0}...)
			array = append(array,back...)
		}
	}
	return array
}

func makeTree(ar []int,i int)*TreeNode{
	if i >= len(ar) || ar[i] == 0{return nil}
	t:=&TreeNode{}
	t.Val = ar[i]
	t.Left = makeTree(ar,2*i+1)
	t.Right = makeTree(ar,2*i+2)
	return t
}

func getLonelyNodes(root *TreeNode) []int {
	var ans []int
	if root == nil{
		return ans
	}else if root.Left == nil && root.Right != nil{
		ans = append(ans,root.Right.Val)
	}else if root.Left != nil && root.Right == nil{
		ans = append(ans,root.Left.Val)
	}
	ans = append(ans,getLonelyNodes(root.Left)...)
	ans = append(ans,getLonelyNodes(root.Right)...)
	return ans
}