再帰

Question

を使用して、バイナリツリーの左葉の合計を取得します。I次のコードを持っていますが、このコードでは問題があるように思われる：私は上記のコードを使用して9得るが、入力[3, 9, 20, null, null, 15, 7, 2, null, null, null, 3, 2, null, null, null, 3]については

private boolean isLeaf(TreeNode node) { 
    if (node == null) 
     return false; 
    if (node.left == null && node.right == null) 
     return true; 
    return false; 
} 

public int sumOfLeftLeaves(TreeNode root) { 
    if (root == null) 
     return 0; 
    if (isLeaf(root.left)) 
     return root.left.val; 
    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); 
} 

答えは12、つまり9 + 3になります。

このコードには何が欠けていますか？

入力配列は、親が位置iにあり、その左の子が2 * i + 1にあり、右の子が2 * i + 2にあるバイナリツリーを表します。

Answer 1

まず問題：

[3, 9, 20, null, null, 15, 7, 2, null, null, null, 3, 2, null, null, null, 3] 

3は、それが子供のように9と20を持って、ルートです。 9には子供がいません、20人は15と7です。 2人はどこに属していますか？ここで

は、Rubyのツリーです：

Node (0) : 3 
    Node (2) : 20 
     Node (6) : 7 
      Node (14) : nil 
      Node (13) : nil 
     Node (5) : 15 
      Node (12) : 2 
      Node (11) : 3 
    Node (1) : 9 
     Node (4) : nil 
      Node (10) : nil 
      Node (9) : nil 
     Node (3) : nil 
      Node (8) : nil 
      Node (7) : 2 
       Node (16) : 3 
       Node (15) : nil 

第二の問題：ノードが左の葉が、右側の枝可能性があり

：

public int sumOfLeftLeaves(TreeNode root) { 
    if (root == null) 
     return 0; 
    if (isLeaf(root.left)) 
     return root.left.val+sumOfLeftLeaves(root.right); 
    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); 
}