最近總結(jié)了一些數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的題目，這是第一篇文章，關(guān)于二叉樹(shù)的。先上二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)：

class TreeNode{ int val; //左孩子 TreeNode left; //右孩子 TreeNode right;}

二叉樹(shù)的題目普遍可以用遞歸和迭代的方式來(lái)解

1. 求二叉樹(shù)的最大深度

int maxDeath(TreeNode node){ if(node==null){ return 0; } int left = maxDeath(node.left); int right = maxDeath(node.right); return Math.max(left,right) + 1;}

2. 求二叉樹(shù)的最小深度

int getMinDepth(TreeNode root){ if(root == null){ return 0; } return getMin(root); } int getMin(TreeNode root){ if(root == null){ return Integer.MAX_VALUE; } if(root.left == null&&root.right == null){ return 1; } return Math.min(getMin(root.left),getMin(root.right)) + 1; }

3. 求二叉樹(shù)中節(jié)點(diǎn)的個(gè)數(shù)

int numOfTreeNode(TreeNode root){ if(root == null){ return 0; } int left = numOfTreeNode(root.left); int right = numOfTreeNode(root.right); return left + right + 1; }

4. 求二叉樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)

int numsOfNoChildNode(TreeNode root){ if(root == null){ return 0; } if(root.left==null&&root.right==null){ return 1; } return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right); }

5. 求二叉樹(shù)中第k層節(jié)點(diǎn)的個(gè)數(shù)

int numsOfkLevelTreeNode(TreeNode root,int k){ if(root == null||k<1){ ? ? ? ? ? ? ? ?return 0; ? ? ? ? ? ?} ? ? ? ? ? ?if(k==1){ ? ? ? ? ? ? ? ?return 1; ? ? ? ? ? ?} ? ? ? ? ? ?int numsLeft = numsOfkLevelTreeNode(root.left,k-1); ? ? ? ? ? ?int numsRight = numsOfkLevelTreeNode(root.right,k-1); ? ? ? ? ? ?return numsLeft + numsRight; ? ? ? ?}

6. 判斷二叉樹(shù)是否是平衡二叉樹(shù)

boolean isBalanced(TreeNode node){ return maxDeath2(node)!=-1; } int maxDeath2(TreeNode node){ if(node == null){ return 0; } int left = maxDeath2(node.left); int right = maxDeath2(node.right); if(left==-1||right==-1||Math.abs(left-right)>1){ return -1; } return Math.max(left, right) + 1; }

7.判斷二叉樹(shù)是否是完全二叉樹(shù)

什么是完全二叉樹(shù)呢？參見(jiàn)

boolean isCompleteTreeNode(TreeNode root){ if(root == null){ return false; } Queue queue = new LinkedList(); queue.add(root); boolean result = true; boolean hasNoChild = false; while(!queue.isEmpty()){ TreeNode current = queue.remove(); if(hasNoChild){ if(current.left!=null||current.right!=null){ result = false; break; } }else{ if(current.left!=null&¤t.right!=null){ queue.add(current.left); queue.add(current.right); }else if(current.left!=null&¤t.right==null){ queue.add(current.left); hasNoChild = true; }else if(current.left==null&¤t.right!=null){ result = false; break; }else{ hasNoChild = true; } } } return result; }

8. 兩個(gè)二叉樹(shù)是否完全相同

boolean isSameTreeNode(TreeNode t1,TreeNode t2){ if(t1==null&&t2==null){ return true; } else if(t1==null||t2==null){ return false; } if(t1.val != t2.val){ return false; } boolean left = isSameTreeNode(t1.left,t2.left); boolean right = isSameTreeNode(t1.right,t2.right); return left&&right; }

9. 兩個(gè)二叉樹(shù)是否互為鏡像

boolean isMirror(TreeNode t1,TreeNode t2){ if(t1==null&&t2==null){ return true; } if(t1==null||t2==null){ return false; } if(t1.val != t2.val){ return false; } return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left); }

10. 翻轉(zhuǎn)二叉樹(shù)or鏡像二叉樹(shù)

TreeNode mirrorTreeNode(TreeNode root){ if(root == null){ return null; } TreeNode left = mirrorTreeNode(root.left); TreeNode right = mirrorTreeNode(root.right); root.left = right; root.right = left; return root; }

11. 求兩個(gè)二叉樹(shù)的最低公共祖先節(jié)點(diǎn)

TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){ if(findNode(root.left,t1)){ if(findNode(root.right,t2)){ return root; }else{ return getLastCommonParent(root.left,t1,t2); } }else{ if(findNode(root.left,t2)){ return root; }else{ return getLastCommonParent(root.right,t1,t2) } } } // 查找節(jié)點(diǎn)node是否在當(dāng)前 二叉樹(shù)中 boolean findNode(TreeNode root,TreeNode node){ if(root == null || node == null){ return false; } if(root == node){ return true; } boolean found = findNode(root.left,node); if(!found){ found = findNode(root.right,node); } return found; }

12. 二叉樹(shù)的前序遍歷

迭代解法

ArrayList preOrder(TreeNode root){ Stack stack = new Stack(); ArrayList list = new ArrayList(); if(root == null){ return list; } stack.push(root); while(!stack.empty()){ TreeNode node = stack.pop(); list.add(node.val); if(node.right!=null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } } return list; }

遞歸解法

ArrayList preOrderReverse(TreeNode root){ ArrayList result = new ArrayList(); preOrder2(root,result); return result; } void preOrder2(TreeNode root,ArrayList result){ if(root == null){ return; } result.add(root.val); preOrder2(root.left,result); preOrder2(root.right,result); }

13. 二叉樹(shù)的中序遍歷

ArrayList inOrder(TreeNode root){ ArrayList list = new ArrayList<(); Stack stack = new Stack(); TreeNode current = root; while(current != null|| !stack.empty()){ while(current != null){ stack.add(current); current = current.left; } current = stack.peek(); stack.pop(); list.add(current.val); current = current.right; } return list; }

14.二叉樹(shù)的后序遍歷

ArrayList postOrder(TreeNode root){ ArrayList list = new ArrayList(); if(root == null){ return list; } list.addAll(postOrder(root.left)); list.addAll(postOrder(root.right)); list.add(root.val); return list; }

15.前序遍歷和后序遍歷構(gòu)造二叉樹(shù)

TreeNode buildTreeNode(int[] preorder,int[] inorder){ if(preorder.length!=inorder.length){ return null; } return myBuildTree(inorder,0,inorder.length-1,preorder,0,preorder.length-1); } TreeNode myBuildTree(int[] inorder,int instart,int inend,int[] preorder,int prestart,int preend){ if(instart>inend){ return null; } TreeNode root = new TreeNode(preorder[prestart]); int position = findPosition(inorder,instart,inend,preorder[start]); root.left = myBuildTree(inorder,instart,position-1,preorder,prestart+1,prestart+position-instart); root.right = myBuildTree(inorder,position+1,inend,preorder,position-inend+preend+1,preend); return root; } int findPosition(int[] arr,int start,int end,int key){ int i; for(i = start;i<=end;i++){ ? ? ? ? ? ?if(arr[i] == key){ ? ? ? ? ? ? ? ?return i; ? ? ? ? ? ?} ? ? ? ?} ? ? ? ?return -1; ? ?}

16.在二叉樹(shù)中插入節(jié)點(diǎn)

TreeNode insertNode(TreeNode root,TreeNode node){ if(root == node){ return node; } TreeNode tmp = new TreeNode(); tmp = root; TreeNode last = null; while(tmp!=null){ last = tmp; if(tmp.val>node.val){ tmp = tmp.left; }else{ tmp = tmp.right; } } if(last!=null){ if(last.val>node.val){ last.left = node; }else{ last.right = node; } } return root; }

17.輸入一個(gè)二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中節(jié)點(diǎn)值的和等于輸入整數(shù)所有的路徑

void findPath(TreeNode r,int i){ if(root == null){ return; } Stack stack = new Stack(); int currentSum = 0; findPath(r, i, stack, currentSum); } void findPath(TreeNode r,int i,Stack stack,int currentSum){ currentSum+=r.val; stack.push(r.val); if(r.left==null&&r.right==null){ if(currentSum==i){ for(int path:stack){ System.out.println(path); } } } if(r.left!=null){ findPath(r.left, i, stack, currentSum); } if(r.right!=null){ findPath(r.right, i, stack, currentSum); } stack.pop(); }

18.二叉樹(shù)的搜索區(qū)間

給定兩個(gè)值 k1 和 k2（k1 < k2）和一個(gè)二叉查找樹(shù)的根節(jié)點(diǎn)。找到樹(shù)中所有值在 k1 到 k2 范圍內(nèi)的節(jié)點(diǎn)。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找樹(shù)的中的節(jié)點(diǎn)值。返回所有升序的節(jié)點(diǎn)值。

ArrayList result; ArrayList searchRange(TreeNode root,int k1,int k2){ result = new ArrayList(); searchHelper(root,k1,k2); return result; } void searchHelper(TreeNode root,int k1,int k2){ if(root == null){ return; } if(root.val>k1){ searchHelper(root.left,k1,k2); } if(root.val>=k1&&root.val<=k2){ ? ? ? ? ? ?result.add(root.val); ? ? ? ?} ? ? ? ?if(root.val

19.二叉樹(shù)的層次遍歷

ArrayList> levelOrder(TreeNode root){ ArrayList> result = new ArrayList>(); if(root == null){ return result; } Queue queue = new LinkedList(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); ArrayList< level = new ArrayList(): for(int i = 0;i < size ;i++){ ? ? ? ? ? ? ? ?TreeNode node = queue.poll(); ? ? ? ? ? ? ? ?level.add(node.val); ? ? ? ? ? ? ? ?if(node.left != null){ ? ? ? ? ? ? ? ? ? ?queue.offer(node.left); ? ? ? ? ? ? ? ?} ? ? ? ? ? ? ? ?if(node.right != null){ ? ? ? ? ? ? ? ? ? ?queue.offer(node.right); ? ? ? ? ? ? ? ?} ? ? ? ? ? ?} ? ? ? ? ? ?result.add(Level); ? ? ? ?} ? ? ? ?return result; ? ?}

20.二叉樹(shù)內(nèi)兩個(gè)節(jié)點(diǎn)的最長(zhǎng)距離

二叉樹(shù)中兩個(gè)節(jié)點(diǎn)的最長(zhǎng)距離可能有三種情況：1.左子樹(shù)的最大深度+右子樹(shù)的最大深度為二叉樹(shù)的最長(zhǎng)距離2.左子樹(shù)中的最長(zhǎng)距離即為二叉樹(shù)的最長(zhǎng)距離3.右子樹(shù)種的最長(zhǎng)距離即為二叉樹(shù)的最長(zhǎng)距離因此，遞歸求解即可

private static class Result{ int maxDistance; int maxDepth; public Result() { } public Result(int maxDistance, int maxDepth) { this.maxDistance = maxDistance; this.maxDepth = maxDepth; } } int getMaxDistance(TreeNode root){ return getMaxDistanceResult(root).maxDistance; } Result getMaxDistanceResult(TreeNode root){ if(root == null){ Result empty = new Result(0,-1); return empty; } Result lmd = getMaxDistanceResult(root.left); Result rmd = getMaxDistanceResult(root.right); Result result = new Result(); result.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth) + 1; result.maxDistance = Math.max(lmd.maxDepth + rmd.maxDepth,Math.max(lmd.maxDistance,rmd.maxDistance)); return result; }

21.不同的二叉樹(shù)

給出 n，問(wèn)由 1…n 為節(jié)點(diǎn)組成的不同的二叉查找樹(shù)有多少種？

int numTrees(int n ){ int[] counts = new int[n+2]; counts[0] = 1; counts[1] = 1; for(int i = 2;i<=n;i++){ ? ? ? ? ? ?for(int j = 0;j

22.判斷二叉樹(shù)是否是合法的二叉查找樹(shù)(BST)

一棵BST定義為：節(jié)點(diǎn)的左子樹(shù)中的值要嚴(yán)格小于該節(jié)點(diǎn)的值。節(jié)點(diǎn)的右子樹(shù)中的值要嚴(yán)格大于該節(jié)點(diǎn)的值。左右子樹(shù)也必須是二叉查找樹(shù)。一個(gè)節(jié)點(diǎn)的樹(shù)也是二叉查找樹(shù)。

public int lastVal = Integer.MAX_VALUE; public boolean firstNode = true; public boolean isValidBST(TreeNode root) { // write your code here if(root==null){ return true; } if(!isValidBST(root.left)){ return false; } if(!firstNode&&lastVal >= root.val){ return false; } firstNode = false; lastVal = root.val; if (!isValidBST(root.right)) { return false; } return true; }

深刻的理解這些題的解法思路，在面試中的二叉樹(shù)題目就應(yīng)該沒(méi)有什么問(wèn)題