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

来源：https://www.jianshu.com/p/0190985635eb

先上二叉树的数据结构：

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 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&&current.right!=null){
 queue.add(current.left);
 queue.add(current.right);
 }else if(current.left!=null&&current.right==null){
 queue.add(current.left);
 hasNoChild = true;
 }else if(current.left==null&&current.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 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. 二叉树的中序遍历

 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.二叉树的后序遍历

 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.前序遍历和后序遍历构造二叉树

 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 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.二叉树的搜索区间

 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 searchHelper(root.right,k1,k2);
 }
 }

19.二叉树的层次遍历

 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.二叉树内两个节点的最长距离

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 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) {
 // 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;
 }

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

閱讀更多 javafirst 的文章

關鍵字: 数据结构 技术 来解