# 【数据结构与算法】一起搞定面试中的二叉树题目（二）

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();
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;
}
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){
current = current.left;
}
current = stack.peek();
stack.pop();
current = current.right;
}
return list;
}```

14.二叉树的后序遍历

```ArrayList<Integer> postOrder(TreeNode root){
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null){
return list;
}
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.二叉树的搜索区间

```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){
}
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.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();
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
}
return result;
}```

20.二叉树内两个节点的最长距离

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

```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)

```public int lastVal = Integer.MAX_VALUE;
public boolean firstNode = true;
public boolean isValidBST(TreeNode root) {
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;
}```

0 条评论

• ### CAP 理论 —最通俗易懂的解释

链接：blog.csdn.net/lihao21/article/details/81051631

• ### 【数据结构与算法】一起搞定面试中的二叉树（一）

最近总结了一些数据结构和算法相关的题目，这是二叉树相关面试题的总结，是用java实现的，由于篇幅有限，因此分为两部分，这是第一部分总结。先上二叉树的数据结构：

• ### Python | 21行轻松搞定拼写检查器

链接：http://blog.csdn.net/Pwiling/article/details/50573650

• ### LeetCode 222. Count Complete Tree Nodes(二分+位运算)

题解：DFS 或者BFS都太low，我们可以用O(log(n)^2)的效率解决，n为节点个数，log(n)就是树的高度。

• ### 面试前准备：二叉树高频面试题和答案

面试中最常考的说法题主要是：数组、链表、二叉树、Map，深刻的理解上面二叉树算法题的解法思路，在面试中的二叉树题目就应该没有什么问题，祝大家面试顺利。

• ### LeetCode：111_Minimum Depth of Binary Tree | 二叉树的最小深度 | Easy

要求：此题正好和Maximum Depth of Binary Tree一题是相反的，即寻找二叉树的最小的深度值：从根节点到最近的叶子节点的距离。 结题思路：和...

• ### 二叉树实战 22 题，速度收藏吧！

深刻的理解这些题的解法思路，在面试中的二叉树题目就应该没有什么问题，甚至可以怒他，哈哈。

• ### 算法篇：树之树的高度

https://leetcode-cn.com/problems/balanced-binary-tree/

• ### 剑指Offer-平衡二叉树

package Tree; /** * 平衡二叉树 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 * 平衡二叉树（Balanced Binary ...

• ### 算法：递归和分治-理论

一说起循环，大家都会说一个例子：“从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山...” 这...