UVa＃112樹總結

Question

我正在處理UVa #112 Tree Summing。我有我認爲應該是一個有效的解決方案，但由於我對這個問題存在基本的誤解，所以沒有被在線法官接受。請看下面的輸入：

-1 (-1()()) 
77 (77(1()())()) 

或圖解，樹木看起來像：

-1    77 
/ \   /\ 
() ()  1 () 
      /\ 
      () () 

根據至少兩個工作方案，對上述輸入正確的輸出是：

yes 
no 

但是，我不明白爲什麼第二個應該是'不'。它看起來像樹的最右邊路徑應該給予適當的總和。我錯過了什麼？

Answer 1

簡單。

樹：

(77(1()())()) 

葉是這樣的形式：（整數（）（））

因此樹只有一個葉：（1（）（））

該葉節點的總和爲78. 78不是77.結果：no。

你認爲是最右邊的路徑，沒有根據定義。

第一棵樹：

(-1()()) 

這僅僅是一個單一的葉節點。一條路。總和是-1。 -1 = -1。結果：是。

我們可以用一個Lisp程序檢查：

(defun leaf-p (node) 
    "is the node a leaf?" 
    (and (= (length node) 3) 
     (integerp (first node)) 
     (null (second node)) 
     (null (third node)))) 

(defun path-sums (tree) 
    "returns a list of all sums for each path" 
    (if (leaf-p tree) 
     (list (first tree)) 
    (mapcar (lambda (s) 
       (+ (first tree) s)) 
      (append (when (second tree) 
         (path-sums (second tree))) 
        (when (third tree) 
         (path-sums (third tree))))))) 

(defun tree-sum-p (sum tree) 
    (member sum (path-sums tree))) 

CL-USER 223 > (path-sums '(-1()())) 
(-1) 

CL-USER 224 > (path-sums '(77(1()())())) 
(78)