1.給定一棵完全二叉樹的頭節點head，求其中的節點個數
遞歸的方法，時間復雜度為O((logN)2)

首先遞歸出頭節點的左子樹的最大深度H，之后再遞歸頭節點的右子樹的深度是否等于H，若相等則表示，頭節點的左子樹加上頭節點的節點數為2^(H-1)-1+1，遞歸頭節點的右子樹即可。若頭節點的右子樹的深度為H-1，則表示頭節點的右子樹加上頭節點的總節點數為2^(H-2)-1+1,遍歷頭節點的左子樹即可。

public static int bs(Node node, int l, int h){if(l == h){return 1;}if(mostLeftLevel(node.right, l+1) == h){return (1 << (h-l)) + bs(node.right, l +1, h);}else{return (1 << (h - l - 1)) + bs(node.left, l + 1, h);} } public static int mostLeftLevel(Node node, int level){while(node != null){level++;node = node.left;}return level - 1; }
2.規定一個字符串類型的數組，其中不含有重復的字符串，如果其中某一個字符串是另一個字符串的前綴，返回true；如果沒有任何一個字符串是另一個字符串的前綴，返回false
前綴樹，把字符掛在邊上，只需要把字符串都遍歷一遍即可解決，若一個字符串遍歷結束之后沒有添加邊，則其為之前的一個字符串的前綴，若其遍歷到另一個字符串的結尾節點之后還需要添加邊，則之前的字符串為當前字符串的前綴

public static class Tries{private HashMap<Character, Tries> children = new HashMap<Character, Tries>();private boolean end = false;public boolean addAndCheck(char[] chs, int i){if(end){return true;}if(i == chs.length){end = true;return !children.isEmpty();}if(!children.containsKey(chs[i])){children.put(chs[i], new Tries());}return children.get(chs[i].addAndCheck(chs, i + 1));} }

總結

以上是生活随笔為你收集整理的有关完全二叉树求节点数和前缀树求字符串是否重复的两道算法题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。