本文共 15598 字，大约阅读时间需要 51 分钟。
最近总结了二叉树的题目。
先上二叉树的数据结构：class TreeNode{ public int val; public TreeNode left; //左孩子 public TreeNode right; //右孩子 public TreeNode(int val){ this.val = val; }} 二叉树的题目普遍可以用递归和迭代的方式来解
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;} 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; } int numOfTreeNode(TreeNode root){ if(root == null){ return 0; } int left = numOfTreeNode(root.left); int right = numOfTreeNode(root.right); return left + right + 1; } 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); } ②若K等于1，第1层就是树根，根只有一个，返回1；
③若K大于1，返回左子树中第K-1层结点个数 加上 右子树中第K-1层结点的个数； 因为，第K层结点，相对于根的左子树 和 右子树 而言，就是第K-1层结点；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; } public boolean IsBalanced_Solution(TreeNode root) { if(root == null) return true; if(Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1) return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right); else return false; } public int getDepth(TreeNode root){ if(root == null) return 0; int left = getDepth(root.left); int right = getDepth(root.right); return 1 + (left>right?left:right); } 什么是完全二叉树呢？
//思路：层次遍历二叉树，一旦某个节点没有左孩子或右孩子，则队列中接下来的节点不能有孩子。public class JudgeCompleteBT { public static void main(String[] args) { TreeNode root = new TreeNode(0); TreeNode node1 = new TreeNode(1); TreeNode node2 = new TreeNode(2); TreeNode node3 = new TreeNode(3); TreeNode node4 = new TreeNode(4); root.left = node1; root.right = node2; node1.left = node3;// node2.right = node4; boolean res = IsComplete(root); System.out.println(res); } public static boolean IsComplete(TreeNode root) { if (root == null) { return true; } boolean noChild = false; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); if (cur.left != null) { //如果无孩子标记被置为true，则queue中不应该再有子元素 if (noChild) { return false; } queue.offer(cur.left); }else { //一旦某元素没有左节点或右节点，则之后所有的元素都不应该有子元素 //并且该元素不应该有右节点 noChild = true; } if (cur.right != null) { //如果无孩子标记被置为true，则queue中不应该再有子元素 if (noChild) { return false; } queue.offer(cur.right); }else { //一旦某元素没有左节点或右节点，则之后所有的元素都不应该有子元素 noChild = true; } } return true; }} 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; } 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); } public void Mirror(TreeNode root) { if (root == null) { return; }else { //交换二叉树的左右子树 TreeNode temp = root.left; root.left = root.right; root.right = temp; //递归处理左右孩子 Mirror(root.left); Mirror(root.right); } } 非递归版本如下：
public void Mirror(TreeNode root) { if(root == null) return; LinkedList stack = new LinkedList<>(); TreeNode current = null; //存放出栈的栈顶元素 TreeNode temp = null; stack.push(root); //将根元素入栈 while (! stack.isEmpty()) { current = stack.pop(); //将跟元素出栈，交换跟元素的左右子树 if (current.left != null || current.right != null) { //若左右孩子不为空，则交换左右孩子 temp = current.left; current.left = current.right; current.right = temp; } //将根元素的左右孩子压入栈中 if (current.left != null) { stack.push(current.left); } if (current.right != null) { stack.push(current.right); } } } public static TreeNode lowestCommonAncestor(TreeNode root,TreeNode node1,TreeNode node2) { if (root == null) { return root; } if (root.val == node1.val || root.val == node2.val) { return root; } TreeNode left = lowestCommonAncestor(root.left, node1, node2); TreeNode right = lowestCommonAncestor(root.right, node1, node2); if (left != null && right != null) { return root; }else if (left != null) { return left; }else if (right != null) { return right; } return null; } public ArrayListpreOrder(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; }
public ArrayListpreOrderReverse(TreeNode root){ ArrayList result = new ArrayList (); preOrder2(root,result); return result; } public void preOrder2(TreeNode root,ArrayList result){ if(root == null){ return; } result.add(root.val); preOrder2(root.left,result); preOrder2(root.right,result); }
public static void midOrder(TreeNode treeNode) { System.out.println("In-order:"); if (treeNode != null) { Stack stack = new Stack<>(); while (treeNode != null || !stack.isEmpty()) { if (treeNode != null) { stack.push(treeNode); treeNode = treeNode.left; }else { treeNode = stack.pop(); System.out.println(treeNode.val); treeNode = treeNode.right; } } } } 递归：
//中序遍历-递归 public static void midOrderRe(TreeNode treeNode) { if (treeNode == null) { return; }else { midOrderRe(treeNode.left); //左 System.out.println(treeNode.val); //中 midOrderRe(treeNode.right); //右 } } //后序遍历--递归 public static void postOrderRe(TreeNode treeNode) { if (treeNode == null) { return; }else { postOrderRe(treeNode.left); //左 postOrderRe(treeNode.right); //右 System.out.print(treeNode.val + " "); //中 } } 非递归：
//后序遍历-非递归// 后序遍历递归定义：先左子树，后右子树，再根节点。// 后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。 public static /*ArrayList*/ void postOrder(TreeNode treeNode) { ArrayList res = new ArrayList<>(); if (treeNode == null) { // return res; return; } Stack stack = new Stack<>(); TreeNode cur = treeNode; //用来记录当前访问结点 TreeNode pre = null; // 记录上次访问结点 //先把左枝全入栈 while (cur != null) { stack.push(cur); cur = cur.left; } while (!stack.isEmpty()) { cur = stack.pop(); //如果当前访问结点的右孩子为空 或者 与上次访问结点相同（说明顺序为：右孩子->根） if (cur.right == null || cur.right == pre) { // res.add(cur.val); System.out.print(cur.val + " "); //访问 pre = cur; //更新上次访问结点 }else { //如果为根结点，再次入栈 stack.push(cur); cur = cur.right; //再将其右孩子入栈 while (cur != null) { stack.push(cur); cur = cur.left; //继续放入右孩子的左枝 } } }// return res; }
public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre == null || in == null) return null; if(pre.length == 0 || in.length == 0) return null; return reConstructBinaryTree(pre, 0, pre.length-1, in, 0, in.length-1); } // *@pre 前序遍历数组// *@preStart 前序数组起始位// *@preEnd 前序数组终止位// *@in 中序遍历数组// *@instart 中序遍历数组起始位// *@inEnd 中序遍历数组终止位 public TreeNode reConstructBinaryTree(int[] pre,int preStart,int preEnd,int[] in,int inStart,int inEnd) { if(preStart > preEnd || inStart > inEnd) return null; int root = pre[preStart]; //前序遍历数组的第一个元素就是子树的根结点 TreeNode tree = new TreeNode(root); //根据【前序遍历数组得到的根结点】 在【中序遍历数组】中找到根结点的位置 int rootIndex = 0; for (int i = inStart; i <= inEnd; i++) { if (in[i] == root) { rootIndex = i; break; } } //当前根结点,左子树的节点数/右子树的节点数 int leftCount = rootIndex - inStart; int rightCount = inEnd - rootIndex; //左右子树递归 tree.left = reConstructBinaryTree(pre, preStart + 1, preStart + leftCount, in, inStart, rootIndex - 1); tree.right = reConstructBinaryTree(pre, preStart + leftCount + 1, preEnd, in, rootIndex + 1, inEnd); return tree; //返回树 }} public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) return new TreeNode(val); if (val < root.val) root.left = insertIntoBST(root.left, val); if (val > root.val) root.right = insertIntoBST(root.right, val); return root; } 非递归
public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) { root = new TreeNode(val); } TreeNode node = root; while (node != null) { if (val < root.val) { //左子节点为空，则创建新节点 if (node.left == null) { node.left = new TreeNode(val); break; } node = node.left; } if (val > root.val) { if (node.right == null) { node.right = new TreeNode(val); break; } node = node.right; } } return root; } public class Solution { private ArrayList > pathList = new ArrayList<>(); //保存所有可能的路径 private ArrayList path = new ArrayList<>(); //用来保存路径 public ArrayList > FindPath(TreeNode root,int target) { if(root == null) return pathList; path.add(root.val); target -= root.val; //路径值为0，并且当前节点为叶子节点，则找到一条路径 if (target ==0 && root.left == null && root.right == null) { // 每次找到路径都需要添加一个新的path 不可以直接加path成员变量 这是个引用，不然所有pathList的值都指向同一个path pathList.add(new ArrayList (path)); //注意 } if (root.left != null) { FindPath(root.left, target); } if (root.right != null) { FindPath(root.right, target); } //访问完当前节点，需要删除路径中的最后一个节点，回退至父节点 path.remove(path.size() - 1); return pathList; }} 给定两个值 k1 和 k2（k1 < k2）和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。
ArrayListresult; 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; } //如果k1小于当前节点 if(k1 < root.val){ searchHelper(root.left,k1,k2); } //如果当前节点的值位于k1,k2之间 if(k1 <= root.val && k2 >= root.val){ result.add(root.val); //加入结果中 } //k2大于当前节点的值 if(k2 > root.val){ searchHelper(root.right,k1,k2); } }
ArrayList> Print(TreeNode pRoot) { /**ArrayList > res = new ArrayList<>(); if (pRoot == null) { return res; } Queue queue = new LinkedList<>(); ArrayList layerList = new ArrayList<>(); queue.add(pRoot); int start = 0, end = 1; //end用来记录每层结点的数量 while (! queue.isEmpty()) { TreeNode cur = queue.poll(); layerList.add(cur.val); start++; if (cur.left != null) { queue.add(cur.left); } if (cur.right != null) { queue.add(cur.right); } if (start == end) { end = queue.size(); //下一层结点的数量 start = 0; //start清零 res.add(layerList); //当前层结点加入结果中 layerList = new ArrayList (); } } return res;*/ ArrayList > result = new ArrayList >(); if(pRoot == null){ return result; } Queue queue = new LinkedList (); queue.offer(pRoot); 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; }
二叉树中两个节点的最长距离可能有三种情况：
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; } 给出 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 一棵BST定义为：
节点的左子树中的值要严格小于该节点的值。 节点的右子树中的值要严格大于该节点的值。 左右子树也必须是二叉查找树。 一个节点的树也是二叉查找树。
class Solution { private int last; private boolean isFirst = true; public boolean isValidBST(TreeNode root) { if(root == null){ return true; } if(isValidBST(root.left)){ if(last < root.val || isFirst == true){ isFirst = false; last = root.val; return isValidBST(root.right); } } return false; }} 深刻的理解这些题的解法思路，在面试中的二叉树题目就应该没有什么问题。
这里还有一篇关于二叉树的文章，转载地址：http://fpdgi.baihongyu.com/