面试BAT 却被二叉树秒杀？20 道题帮你一举拿下二叉树算法题

第一题：求二叉树中的节点个数 第二题：求二叉树的最大层数(最大深度)

 第三题：先序遍历/前序遍历

 第四题：中序遍历

 第五题：后序遍历 

第六题：分层遍历 

第七题：求二叉树第K层的节点个数 

第八题：求二叉树第K层的叶子节点个数 

第九题：判断两棵二叉树是否结构相同 

第十题：判断二叉树是不是平衡二叉树 第十一题： 求二叉树的镜像 

第十二题：求二叉树中两个节点的最低公共祖先节点 

第十三题：求二叉树的直径 

第十四题：由前序遍历序列和中序遍历序列重建二叉树 

第十五题： 判断二叉树是不是完全二叉树 

第十六题：树的子结构

 第十七题：二叉树中和为某一值的路径 

第十八题：二叉树的下一个结点 

第十九题：序列化二叉树

 第二十题：二叉搜索树的第k个结点

第一题：求二叉树中的节点个数

递归解法： （1）如果二叉树为空，节点个数为0 （2）如果不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

	public static int getNodeNumRec(TreeNode root) {
 if (root == null) {
 return 0;
 } 
 return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
} 

第二题：二叉树的最大层数(最大深度)

递归解法 ： （1）如果二叉树为空，二叉树的深度为0 （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1

	/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public int maxDepth(TreeNode root) {
 if(root == null)
 return 0;
 return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
 }
} 

LeetCode：Minimum Depth of Binary Tree 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

	lass Solution {
 public int minDepth(TreeNode root) {
 if(root == null)
 return 0;
 int left = minDepth(root.left);
 int right = minDepth(root.right);
 return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
 }
} 

第三题：先序遍历/前序遍历

LeetCode：Binary Tree Preorder Traversal 给定二叉树，返回其节点值的前序遍历。

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

	import java.util.Stack;
class Solution {
 public List<Integer> preorderTraversal(TreeNode root) {
 LinkedList<Integer> res = new LinkedList<>();
 if(root == null)
 return res;
 Stack<TreeNode> stack = new Stack<>();
 stack.push(root);
 while(!stack.isEmpty()){
 TreeNode node = stack.pop();
 res.add(node.val);
 if(node.right != null){
 stack.push(node.right);
 }
 if(node.left != null){
 stack.push(node.left);
 }
 }
 return res;
 }
} 

	class Solution {
 public List<Integer> preorderTraversal(TreeNode root) {
 List<Integer> res = new ArrayList<Integer>();
 if(root == null)
 return res;
 Stack<TreeNode> stack = new Stack<TreeNode>();
 TreeNode cur = root;
 while(cur != null || !stack.isEmpty()){
 if(cur!=null){
 res.add(cur.val);
 stack.push(cur);
 cur = cur.left;
 }else{
 cur = stack.pop();
 cur = cur.right;
 }
 }
 return res;
 }
} 

第四题：中序遍历

LeetCode：Binary Tree Inorder Traversal 给定二叉树，返回其节点值的中序遍历。

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

	/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public List<Integer> inorderTraversal(TreeNode root) {
 List<Integer> res = new ArrayList<Integer>();
 if(root == null)
 return res;
 
 Stack<TreeNode> stack = new Stack<TreeNode>();
 TreeNode cur = root;
 while(!stack.isEmpty() || cur != null){
 if(cur != null){
 stack.push(cur);
 cur = cur.left;
 }else{
 cur = stack.pop();
 res.add(cur.val);
 cur = cur.right;
 }
 }
 return res;
 }
} 

第五题：后序遍历

Leetcode：Binary Tree Postorder Traversal 给定二叉树，返回其节点值的后序遍历。

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

	/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public List<Integer> postorderTraversal(TreeNode root) {
 LinkedList<Integer> ans = new LinkedList<>();
 Stack<TreeNode> stack = new Stack<>();
 if (root == null) return ans;
 stack.push(root);
 while (!stack.isEmpty()) {
 TreeNode cur = stack.pop();
 //采用逆序插入的方式
 ans.addFirst(cur.val);
 if (cur.left != null) {
 stack.push(cur.left);
 }
 if (cur.right != null) {
 stack.push(cur.right);
 } 
 }
 return ans;
 }
} 

	/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public List<Integer> postorderTraversal(TreeNode root) {
 List<Integer> res = new ArrayList<Integer>();
 
 if(root == null)
 return res;
 
 Stack<TreeNode> stack = new Stack<TreeNode>();
 TreeNode cur = root;
 TreeNode visited = null;
 while(!stack.isEmpty() || cur != null){
 if(cur != null){
 stack.push(cur);
 cur = cur.left;
 }else{
 cur = stack.peek();
 if(cur.right != null && cur.right != visited){
 cur = cur.right;
 }else{
 res.add(cur.val);
 visited = cur;
 stack.pop();
 cur = null;
 }
 }
 }
 return res;
 }
}