二叉树实战 22 题，速度收藏吧！
先上二叉树的数据结构：
classTreeNode{
intval;
//左孩子
TreeNode left;
//右孩子
TreeNode right;
}
二叉树的题目普遍可以用递归和迭代的方式来解
1. 求二叉树的最大深度
intmaxDeath(TreeNode node){
if(node==null){
return0;
}
intleft = maxDeath(node.left);
intright = maxDeath(node.right);
returnMath.max(left,right) +1;
}
2. 求二叉树的最小深度
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. 求二叉树中节点的个数
intnumOfTreeNode(TreeNode root){
if(root ==null){
return0;
}
intleft = numOfTreeNode(root.left);
intright = numOfTreeNode(root.right);
returnleft + right +1;
}
4. 求二叉树中叶子节点的个数
intnumsOfNoChildNode(TreeNode root){
if(root ==null){
return0;
}
if(root.left==null&&root.right==null){
return1;
}
returnnumsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);
}
5. 求二叉树中第k层节点的个数
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. 判断二叉树是否是平衡二叉树
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.判断二叉树是否是完全二叉树
什么是完全二叉树呢？参见
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. 两个二叉树是否完全相同
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. 两个二叉树是否互为镜像
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. 翻转二叉树or镜像二叉树
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. 求两个二叉树的最低公共祖先节点
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)
}
}
}
// 查找节点node是否在当前 二叉树中
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. 二叉树的前序遍历
迭代解法
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. 二叉树的中序遍历
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.二叉树的后序遍历
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.前序遍历和后序遍历构造二叉树
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.在二叉树中插入节点
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.输入一个二叉树和一个整数，打印出二叉树中节点值的和等于输入整数所有的路径
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.二叉树的搜索区间
给定两个值 k1 和 k2（k1 < k2）和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。
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.二叉树的层次遍历
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.二叉树内两个节点的最长距离
二叉树中两个节点的最长距离可能有三种情况：
1.左子树的最大深度+右子树的最大深度为二叉树的最长距离
2.左子树中的最长距离即为二叉树的最长距离
3.右子树种的最长距离即为二叉树的最长距离
因此，递归求解即可
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.不同的二叉树
给出 n，问由 1…n 为节点组成的不同的二叉查找树有多少种？
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.判断二叉树是否是合法的二叉查找树(BST)
一棵BST定义为：
节点的左子树中的值要严格小于该节点的值。
节点的右子树中的值要严格大于该节点的值。
左右子树也必须是二叉查找树。
一个节点的树也是二叉查找树。
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;
}
深刻的理解这些题的解法思路，在面试中的二叉树题目就应该没有什么问题，甚至可以怼他，哈哈。
