先上二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)：
classTreeNode{
intval;
//左孩子
TreeNode left;
//右孩子
TreeNode right;
}
二叉樹(shù)的題目普遍可以用遞歸和迭代的方式來(lái)解
1. 求二叉樹(shù)的最大深度
intmaxDeath(TreeNode node){
if(node==null){
return0;
}
intleft = maxDeath(node.left);
intright = maxDeath(node.right);
returnMath.max(left,right) +1;
}
2. 求二叉樹(shù)的最小深度
intgetMinDepth(TreeNode root){
if(root ==null){
return0;
}
returngetMin(root);
}
intgetMin(TreeNode root){
if(root ==null){
returnInteger.MAX_VALUE;
}
if(root.left ==null&&root.right ==null){
return1;
}
returnMath.min(getMin(root.left),getMin(root.right)) +1;
}
3. 求二叉樹(shù)中節(jié)點(diǎn)的個(gè)數(shù)
intnumOfTreeNode(TreeNode root){
if(root ==null){
return0;
}
intleft = numOfTreeNode(root.left);
intright = numOfTreeNode(root.right);
returnleft + right +1;
}
4. 求二叉樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)
intnumsOfNoChildNode(TreeNode root){
if(root ==null){
return0;
}
if(root.left==null&&root.right==null){
return1;
}
returnnumsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);
}
5. 求二叉樹(shù)中第k層節(jié)點(diǎn)的個(gè)數(shù)
intnumsOfkLevelTreeNode(TreeNode root,intk){
if(root ==null||k<1){
return0;
}
if(k==1){
return1;
}
intnumsLeft = numsOfkLevelTreeNode(root.left,k-1);
intnumsRight = numsOfkLevelTreeNode(root.right,k-1);
returnnumsLeft + numsRight;
}
6. 判斷二叉樹(shù)是否是平衡二叉樹(shù)
booleanisBalanced(TreeNode node){
returnmaxDeath2(node)!=-1;
}
intmaxDeath2(TreeNode node){
if(node ==null){
return0;
}
intleft = maxDeath2(node.left);
intright = maxDeath2(node.right);
if(left==-1||right==-1||Math.abs(left-right)>1){
return-1;
}
returnMath.max(left, right) +1;
}
7.判斷二叉樹(shù)是否是完全二叉樹(shù)
什么是完全二叉樹(shù)呢敷矫？參見(jiàn)
booleanisCompleteTreeNode(TreeNode root){
if(root ==null){
returnfalse;
}
Queue queue =newLinkedList();
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);
}elseif(current.left!=null&¤t.right==null){
queue.add(current.left);
hasNoChild =true;
}elseif(current.left==null&¤t.right!=null){
result =false;
break;
}else{
hasNoChild =true;
}
}
}
returnresult;
}
8. 兩個(gè)二叉樹(shù)是否完全相同
booleanisSameTreeNode(TreeNode t1,TreeNode t2){
if(t1==null&&t2==null){
returntrue;
}
elseif(t1==null||t2==null){
returnfalse;
}
if(t1.val != t2.val){
returnfalse;
}
booleanleft = isSameTreeNode(t1.left,t2.left);
booleanright = isSameTreeNode(t1.right,t2.right);
returnleft&&right;
}
9. 兩個(gè)二叉樹(shù)是否互為鏡像
booleanisMirror(TreeNode t1,TreeNode t2){
if(t1==null&&t2==null){
returntrue;
}
if(t1==null||t2==null){
returnfalse;
}
if(t1.val != t2.val){
returnfalse;
}
returnisMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
}
10. 翻轉(zhuǎn)二叉樹(shù)or鏡像二叉樹(shù)
TreeNodemirrorTreeNode(TreeNode root){
if(root ==null){
returnnull;
}
TreeNode left = mirrorTreeNode(root.left);
TreeNode right = mirrorTreeNode(root.right);
root.left = right;
root.right = left;
returnroot;
}
11. 求兩個(gè)二叉樹(shù)的最低公共祖先節(jié)點(diǎn)
TreeNodegetLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){
if(findNode(root.left,t1)){
if(findNode(root.right,t2)){
returnroot;
}else{
returngetLastCommonParent(root.left,t1,t2);
}
}else{
if(findNode(root.left,t2)){
returnroot;
}else{
returngetLastCommonParent(root.right,t1,t2)
}
}
}
// 查找節(jié)點(diǎn)node是否在當(dāng)前 二叉樹(shù)中
booleanfindNode(TreeNode root,TreeNode node){
if(root ==null|| node ==null){
returnfalse;
}
if(root == node){
returntrue;
}
booleanfound = findNode(root.left,node);
if(!found){
found = findNode(root.right,node);
}
returnfound;
}
12. 二叉樹(shù)的前序遍歷
迭代解法
ArrayList preOrder(TreeNode root){
Stackstack=newStack();
ArrayListlist=newArrayList();
if(root == null){
returnlist;
}
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);
}
}
returnlist;
}
遞歸解法
ArrayListpreOrderReverse(TreeNode root){
ArrayList result =newArrayList();
preOrder2(root,result);
returnresult;
}
voidpreOrder2(TreeNode root,ArrayList<Integer> result){
if(root ==null){
return;
}
result.add(root.val);
preOrder2(root.left,result);
preOrder2(root.right,result);
}
13. 二叉樹(shù)的中序遍歷
ArrayList inOrder(TreeNode root){
ArrayListlist=newArrayList<();
Stackstack=newStack();
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;
}
returnlist;
}
14.二叉樹(shù)的后序遍歷
ArrayList postOrder(TreeNode root){
ArrayListlist=newArrayList();
if(root ==null){
returnlist;
}
list.addAll(postOrder(root.left));
list.addAll(postOrder(root.right));
list.add(root.val);
returnlist;
}
15.前序遍歷和后序遍歷構(gòu)造二叉樹(shù)
TreeNodebuildTreeNode(int[] preorder,int[] inorder){
if(preorder.length!=inorder.length){
returnnull;
}
returnmyBuildTree(inorder,0,inorder.length-1,preorder,0,preorder.length-1);
}
TreeNodemyBuildTree(int[] inorder,intinstart,intinend,int[] preorder,intprestart,intpreend){
if(instart>inend){
returnnull;
}
TreeNode root =newTreeNode(preorder[prestart]);
intposition = 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);
returnroot;
}
intfindPosition(int[] arr,intstart,intend,intkey){
inti;
for(i = start;i<=end;i++){
if(arr[i] == key){
returni;
}
}
return-1;
}
16.在二叉樹(shù)中插入節(jié)點(diǎn)
TreeNodeinsertNode(TreeNode root,TreeNode node){
if(root == node){
returnnode;
}
TreeNode tmp =newTreeNode();
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;
}
}
returnroot;
}
17.輸入一個(gè)二叉樹(shù)和一個(gè)整數(shù)例获，打印出二叉樹(shù)中節(jié)點(diǎn)值的和等于輸入整數(shù)所有的路徑
voidfindPath(TreeNode r,inti){
if(root == null){
return;
}
Stackstack=newStack();
intcurrentSum =0;
findPath(r, i,stack, currentSum);
}
voidfindPath(TreeNode r,inti,Stackstack,intcurrentSum){
currentSum+=r.val;
stack.push(r.val);
if(r.left==null&&r.right==null){
if(currentSum==i){
for(intpath: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;
ArrayListsearchRange(TreeNode root,intk1,intk2){
result =newArrayList();
searchHelper(root,k1,k2);
returnresult;
}
voidsearchHelper(TreeNode root,intk1,intk2){
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
searchHelper(root.right,k1,k2);
}
}
19.二叉樹(shù)的層次遍歷
ArrayList> levelOrder(TreeNode root){
ArrayList> result =newArrayList>();
if(root == null){
returnresult;
}
Queuequeue=newLinkedList();
queue.offer(root);
while(!queue.isEmpty()){
intsize =queue.size();
ArrayList< level =newArrayList():
for(inti =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);
}
returnresult;
}
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)距離
因此怎茫，遞歸求解即可
privatestaticclassResult{
intmaxDistance;
intmaxDepth;
publicResult(){
}
publicResult(intmaxDistance,intmaxDepth){
this.maxDistance = maxDistance;
this.maxDepth = maxDepth;
}
}
intgetMaxDistance(TreeNode root){
returngetMaxDistanceResult(root).maxDistance;
}
ResultgetMaxDistanceResult(TreeNode root){
if(root ==null){
Result empty =newResult(0,-1);
returnempty;
}
Result lmd = getMaxDistanceResult(root.left);
Result rmd = getMaxDistanceResult(root.right);
Result result =newResult();
result.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth) +1;
result.maxDistance = Math.max(lmd.maxDepth + rmd.maxDepth,Math.max(lmd.maxDistance,rmd.maxDistance));
returnresult;
}
21.不同的二叉樹(shù)
給出 n收壕，問(wèn)由 1…n 為節(jié)點(diǎn)組成的不同的二叉查找樹(shù)有多少種？
intnumTrees(intn ){
int[] counts =newint[n+2];
counts[0] =1;
counts[1] =1;
for(inti =2;i<=n;i++){
for(intj =0;j
counts[i] += counts[j] * counts[i-j-1];
}
}
returncounts[n];
}
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ù)祥山。
publicintlastVal = Integer.MAX_VALUE;
publicbooleanfirstNode =true;
publicbooleanisValidBST(TreeNode root){
// write your code here
if(root==null){
returntrue;
}
if(!isValidBST(root.left)){
returnfalse;
}
if(!firstNode&&lastVal >= root.val){
returnfalse;
}
firstNode =false;
lastVal = root.val;
if(!isValidBST(root.right)) {
returnfalse;
}
returntrue;
}
深刻的理解這些題的解法思路圃验，在面試中的二叉樹(shù)題目就應(yīng)該沒(méi)有什么問(wèn)題，甚至可以懟他缝呕，哈哈损谦。
