一篇文章搞定面試中的二叉樹題目(java實現)

摘要： 最近總結了一些資料結構和演算法相關的題目，這是第一篇文章，關於二叉樹的。 先上二叉樹的資料結構： class TreeNode{ int val; //左孩子 TreeNode left; //右孩子 TreeNode right; ...

最近總結了一些資料結構和演算法相關的題目，這是第一篇文章，關於二叉樹的。

先上二叉樹的資料結構：

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

二叉樹的題目普遍可以用遞迴和迭代的方式來解

1.求二叉樹的最大深度

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.求二叉樹的最小深度

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,求二叉樹中節點的個數

int numOfTreeNode(TreeNode root){
if(root == null){
return 0;

}
int left = numOfTreeNode(root.left);
int right = numOfTreeNode(root.right);
return left + right + 1;
}

4,求二叉樹中葉子節點的個數

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.求二叉樹中第k層節點的個數

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.判斷二叉樹是否是平衡二叉樹

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.判斷二叉樹是否是完全二叉樹

boolean isCompleteTreeNode(TreeNode root){
if(root == null){
return false;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
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.兩個二叉樹是否完全相同

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.兩個二叉樹是否互為映象

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.翻轉二叉樹or映象二叉樹

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.求兩個二叉樹的最低公共祖先節點

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)
}
}
}
// 查詢節點node是否在當前 二叉樹中
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.二叉樹的前序遍歷

迭代解法

ArrayList<Integer> preOrder(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> list = new ArrayList<Integer>();
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<Integer> preOrderReverse(TreeNode root){
ArrayList<Integer> result = new ArrayList<Integer>();
preOrder2(root,result);
return result;

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

13.二叉樹的中序遍歷

ArrayList<Integer> inOrder(TreeNode root){
ArrayList<Integer> list = new ArrayList<<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
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.二叉樹的後序遍歷

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

15.前序遍歷和後序遍歷構造二叉樹

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.在二叉樹中插入節點

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.輸入一個二叉樹和一個整數，打印出二叉樹中節點值的和等於輸入整數所有的路徑

void findPath(TreeNode r,int i){
if(root == null){
return;
}
Stack<Integer> stack = new Stack<Integer>();
int currentSum = 0;
findPath(r, i, stack, currentSum);

}
void findPath(TreeNode r,int i,Stack<Integer> 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.二叉樹的搜尋區間

給定兩個值 k1 和 k2（k1 < k2）和一個二叉查詢樹的根節點。找到樹中所有值在 k1 到 k2 範圍內的節點。即列印所有x (k1 <= x <= k2) 其中 x 是二叉查詢樹的中的節點值。返回所有升序的節點值

ArrayList<Integer> result;
ArrayList<Integer> searchRange(TreeNode root,int k1,int k2){
result = new ArrayList<Integer>();
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<k2){
searchHelper(root.right,k1,k2);
}
}

19.二叉樹的層次遍歷

ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(root == null){
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
ArrayList<<Integer> level = new ArrayList<Integer>():
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.二叉樹內兩個節點的最長距離

二叉樹中兩個節點的最長距離可能有三種情況：

1.左子樹的最大深度+右子樹的最大深度為二叉樹的最長距離

2.左子樹中的最長距離即為二叉樹的最長距離

3.右子樹種的最長距離即為二叉樹的最長距離

因此，遞迴求解即可

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.不同的二叉樹

給出 n，問由 1...n 為節點組成的不同的二叉查詢樹有多少種？

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<i;j++){
counts[i] += counts[j] * counts[i-j-1];
}
}
return counts[n];
}

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

一棵BST定義為：

節點的左子樹中的值要嚴格小於該節點的值。

節點的右子樹中的值要嚴格大於該節點的值。

左右子樹也必須是二叉查詢樹。

一個節點的樹也是二叉查詢樹。

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;
}