棰樼洰鎻忚堪杩欐槸LeetCode涓婄殑513.姹傛爲宸︿笅瑙掔殑鍊硷紝闅惧害涓瓑銆俆ag:"BFS"鈥嬧€?"DFS","TreeTraversal"缁欏畾涓€妫典簩鍙夋爲鐨勬牴鑺傜偣root锛岃鎵惧嚭浜屽弶鏍戞渶搴曢儴鏈€宸﹁竟鑺傜偣鐨勫€笺€傚亣璁句簩鍙夋爲涓嚦灏戞湁涓€涓妭鐐广€傜ず渚?锛氳緭鍏ワ細root=[2,1,3]杈撳嚭锛?绀轰緥2锛氳緭鍏ワ細[1,2,3,4,null,5,6,null,null,7]杈撳嚭锛?鎻愮ず锛氫簩鍙夋爲of鑺傜偣鏁扮殑鑼冨洿鏄?[1,10^4]$$-2^{31}<=Node.val<=2^{31}-1$BFS浣跨敤BFS杩涜鈥滃眰搴忛亶鍘嗏€濓紝姣忔鐢ㄥ綋鍓嶅眰鐨勭涓€涓妭鐐规潵鏇存柊ans锛屽綋BFS缁撴潫鏃讹紝ans瀛樺偍鏈€鍚庝竴灞傜殑鏈€宸﹁竟鑺傜偣銆備唬鐮侊細classSolution{publicintfindBottomLeftValue(TreeNoderoot){Dequed=newArrayDeque<>();d.addLast(鏍?;intans=0;while(!d.isEmpty()){intsz=d.size();ans=d.peek().val;while(sz-->0){TreeNodepoll=d.pollFirst();if(poll.left!=null)d.addLast(poll.left);if(poll.right!=null)d.addLast(poll.right);}}杩斿洖绛旀锛泒}鏃堕棿澶嶆潅搴︼細$O(n)$绌洪棿澶嶆潅搴︼細鏈€鍧忔儏鍐典笅锛屾墍鏈夎妭鐐归兘鍦ㄥ悓涓€灞傦紝澶嶆潅搴︿负$O(n)$DFS鍚岀悊锛孌FS鍙互鐢ㄤ簬鏍戠殑閬嶅巻锛屾瘡娆FS涓綋鍓嶈妭鐐圭殑宸﹀瓙鏍戜紭鍏堬紝褰撳墠娣卞害depth姣忔绗竴娆℃悳绱㈡椂蹇呴』鏄綋鍓嶆繁搴︽渶宸﹁竟鐨勮妭鐐癸紝姝ゆ椂鐢ㄥ綋鍓嶈妭鐐瑰€兼洿鏂癮ns銆備唬鐮侊細classSolution{intmax,ans;publicintfindBottomLeftValue(TreeNoderoot){dfs(root,1);杩斿洖绛旀锛泒voiddfs(TreeNoderoot,intdepth){if(root==null)return;濡傛灉锛堟繁搴?鏈€澶у€硷級{鏈€澶у€?娣卞害锛沘ns=root.val;}dfs(root.left,depth+1);dfs(root.right,depth+1);}}鏃堕棿澶嶆潅搴︼細$O(n)$绌洪棿澶嶆潅搴︼細鏈€鍧忔儏鍐典笅锛岄€€鍖栨垚涓€鏉￠摼锛岄€掑綊娣卞害涓?n$銆傚鏉傚害鏄?O(n)$鏈€鍚庯紝杩欐槸鎴戜滑鈥滃埛LeetCode鈥濈郴鍒楁枃绔犱腑鐨勭513绡囨枃绔犮€傝绯诲垪浜?021/01/01寮€濮嬨€傛埅鑷冲紑璇炬棩鏈燂紝LeetCode鍏辨湁1916閬撻锛屽叾涓儴鍒嗛鐩负閿佸畾棰橈紝鎴戜滑浼氬厛瀹屾垚鎵€鏈夎В閿侀銆傛湰绯诲垪鏂囩珷闄や簡璁茶В瑙ｉ鎬濊矾澶栵紝浼氬敖鍙兘缁欏嚭鏈€绠€娲佺殑浠ｇ爜銆傚鏋滄秹鍙婇€氱敤鏂规锛屼細鏈夌浉搴旂殑浠ｇ爜妯℃澘銆備负浜嗘柟渚垮悓瀛︿滑鍦ㄧ數鑴戜笂璋冭瘯鍜屾彁浜や唬鐮侊紝鎴戝缓绔嬩簡涓€涓浉鍏崇殑浠撳簱锛歨ttps://github.com/SharingSou...銆傚湪浠撳簱鍦板潃鍙互鐪嬪埌绯诲垪鏂囩珷鐨勮В娉曢摼鎺ャ€佺郴鍒楁枃绔犲搴旂殑浠ｇ爜銆丩eetCode鍘熼閾炬帴浠ュ強鍏朵粬浼橀€夎В娉曘€傛洿澶氬叏闈㈢儹闂ㄧ殑鈥滅瑪璇?闈㈣瘯鈥濈浉鍏宠祫璁紝璇疯闂帓鐗堣揪浜哄疂鍏告柊鍩哄湴馃帀馃帀
