討論區快速選單
知識庫快速選單
將BI融合到Excel資料分析中 網路投保旅行平安險 程式設計俱樂部Facebook粉絲團
[ 回上頁 ] [ 討論區發言規則 ]
判斷是否為二元樹
更改我的閱讀文章字型大小
作者 : aa25621166(大頭)
[ 貼文 2 | 人氣 0 | 評價 0 | 評價/貼文 0 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2014/5/2 下午 11:12:42
判斷所給的資料是否可組成二元樹可以就印出二元樹不可以則印出wrong
二元樹最多4層(不含樹根)
EX1:資料:(5,) (4,L) (13,LR) (8,R) (4,RL) (7,RR)

     5(樹根)
     4 (L) 8 (R)
     13(LR) 4(RL)7(RR)

為二元樹所以則印出上圖(印出數字即可)
EX2:(6,) (3,L) (13,LL) (5,LR) (4,RL) (7,RR)
    
     6
     3
     13 5 4 7

因為沒有R所以不為二元樹則印出wrong
EX3:(6,) (3,L) (13,LL)(1,R)(5,LR) (4,RL) (7,RR)(2,L)
    
     6
     3 1
     13 5 4 7

因為L有2個值所以有衝突視為非二元樹則印出wrong
作者 : ozzy123(ozzy) 資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4465 | 人氣 37262 | 評價 10860 | 評價/貼文 2.43 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2014/5/3 上午 08:10:05
>因為沒有R所以不為二元樹則印出wrong
>EX3:(6,) (3,L) (13,LL)(1,R)(5,LR) (4,RL) (7,RR)(2,L)
>
> 6
> 3 1
> 13 5 4 7


 a little suggestion
 For this example , from the most left item to most right item , you may regard each item (node ) as a linked list node , it should look like this structure
[value | link]
So you can link them to a linked list , like this
[ 6 | Null ] -> [ 3 | L ] -> [ 13 | LL ] -> [ 1 | R ] -> -> [ 5 | LR ] -> [ 7 | RR ] -> [ 4 | RL ] -> [ 2 | L ]

Then you start comparing all nodes from 1st node to last node , it needs O(n^2) time complexity
1+2+3+4+ ...+ n = O(n^2)

if you can construct a binary tree , you just need O(k) , k is the depth of node .

Basically , you just justify whether the node has existed or not.
 

作者 : yihcheng(yihcheng)
[ 貼文 137 | 人氣 2 | 評價 770 | 評價/貼文 5.62 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/6/19 下午 12:55:55
這題以前考試有寫過,把程式碼列在下供你參考

     public bool IsValidBST(TreeNode root)
     {
     return BST(root, null, null);
     }

     bool BST(TreeNode node, int? min, int? max)
     {
     if (node == null) return true;
     if (min == null && max == null)
     {
     return BST(node.left, min, node.val ) && BST(node.right, node.val , max);
     }
     else if (min != null && max == null)
     {
     if (node.val > min )
     return BST(node.left, min, node.val) && BST(node.right, node.val, max);
     }
     else if (min == null && max !=null)
     {
     if ( node.val < max)
     return BST(node.left, min, node.val) && BST(node.right, node.val, max);
     }
     else
     {
     if (node.val > min && node.val < max)
     return BST(node.left, min, node.val) && BST(node.right, node.val, max);
     }
     return false;
     }
 板主 : Daniel
 > 資訊類作業 - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - 資訊類作業 - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
資訊類作業
1 Raymond 4540 
2 Ben 2880 
3 青衫 2260 
4 ozzy 1540 
5 HKLN.net 1010 
6 Daniel 780 
7 joe 740 
8 小朱 570 
9 Benson 440 
10 鬼翼@娃娃魚 400 
資訊類作業
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2018 程式設計俱樂部 http://www.programmer-club.com.tw/
0.0546875