最近总结了一些数据结构和算法相关的题目,这是第一篇文章,关于二叉树的。
先上二叉树的数据结构:
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){ <span class="" style="font-size: inherit;line-height: inherit;color: rgb(248, 35, 117);word-wrap: inherit !important;word-break: inherit !important;white-space: inh