数据结构之二叉树总篇（Java）

前言

面试中的树都是二叉树，即有左右两个节点的树 牢记：root.left表示左子树，root.right表示右子树，通过树的递归解决问题

二叉树定义

123456789101112

public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}

求二叉树中节点的个数

递归

12345678910111213

/** * 求二叉树中的节点个数递归解法： O(n) * （1）如果二叉树为空，节点个数为0 * （2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + * 右子树节点个数 + 1 */ public static int getNodeNumRec(TreeNode root) { if (root == null) { return 0; } else { return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1; } }

非递归：迭代

123456789101112131415161718192021222324252627

/** * 求二叉树中的节点个数迭代解法O(n)： * 基本思想同LevelOrderTraversal， * 即用一个Queue，在Java里面可以用LinkedList来模拟 */ public static int getNodeNum(TreeNode root) { if(root == null){ return 0; } int count = 1; Queue queue = new LinkedList(); queue.add(root); while(!queue.isEmpty()){ TreeNode cur = queue.remove(); // 从队头位置移除 if(cur.left != null){ // 如果有左孩子，加到队尾 queue.add(cur.left); count++; } if(cur.right != null){ // 如果有右孩子，加到队尾 queue.add(cur.right); count++; } } return count; }

求树的深度（高）

递归:

1234567891011121314

/** * 求二叉树的深度（高度） 递归解法： O(n) * （1）如果二叉树为空，二叉树的深度为0 * （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1 */ public static int getDepthRec(TreeNode root) { if (root == null) { return 0; } int leftDepth = getDepthRec(root.left); int rightDepth = getDepthRec(root.right); return Math.max(leftDepth, rightDepth) + 1; }

非递归

12345678910111213141516171819202122232425262728293031323334353637

/** * 求二叉树的深度（高度） 迭代解法： O(n) * 基本思想同LevelOrderTraversal，还是用一个Queue */ public static int getDepth(TreeNode root) { if(root == null){ return 0; } int depth = 0; // 深度 int currentLevelNodes = 1; // 当前Level，node的数量 int nextLevelNodes = 0; // 下一层Level，node的数量 LinkedList queue = new LinkedList(); queue.add(root); while( !queue.isEmpty() ){ TreeNode cur = queue.remove(); // 从队头位置移除 currentLevelNodes--; // 减少当前Level node的数量 if(cur.left != null){ // 如果有左孩子，加到队尾 queue.add(cur.left); nextLevelNodes++; // 并增加下一层Level node的数量 } if(cur.right != null){ // 如果有右孩子，加到队尾 queue.add(cur.right); nextLevelNodes++; } if(currentLevelNodes == 0){ // 说明已经遍历完当前层的所有节点 depth++; // 增加高度 currentLevelNodes = nextLevelNodes; // 初始化下一层的遍历 nextLevelNodes = 0; } } return depth; }

前序遍历

即：先根遍历

递归

12345678

public static void preorderTraversalRec(TreeNode root) { if (root == null) { return; } System.out.print(root.val + ' '); preorderTraversalRec(root.left); preorderTraversalRec(root.right); }

非递归：

递归->非递归

利用栈

1234567

创建栈将根节点压入栈While 栈非空 弹出一个节点 打印它的值 If 存在右节点，将右节点压入栈 IF 存在左节点，将左节点压入栈

代码实现：

12345678910111213141516171819202122232425

/** * 前序遍历迭代解法：用一个辅助stack，总是把右孩子放进栈 * */ public static void preorderTraversal(TreeNode root) { if(root == null){ return; } Stack stack = new Stack(); // 辅助stack stack.push(root); while( !stack.isEmpty() ){ TreeNode cur = stack.pop(); // 出栈栈顶元素 System.out.print(cur.val + ' '); // 关键点：要先压入右孩子，再压入左孩子，这样在出栈时会先打印左孩子再打印右孩子 if(cur.right != null){ stack.push(cur.right); } if(cur.left != null){ stack.push(cur.left); } } }

中序遍历

即：中根遍历

递归：

12345678910111213

/** * 中序遍历递归解法 * （1）如果二叉树为空，空操作。 * （2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树 */ public static void inorderTraversalRec(TreeNode root) { if (root == null) { return; } inorderTraversalRec(root.left); System.out.print(root.val + ' '); inorderTraversalRec(root.right); }

非递归：

1234567891011121314151617181920212223242526272829303132

/** * 中序遍历迭代解法 ，用栈先把根节点的所有左孩子都添加到栈内， * 然后输出栈顶元素，再处理栈顶元素的右子树 * 还有一种方法能不用递归和栈，基于线索二叉树的方法，较麻烦以后补上 * http://www./inorder-tree-traversal-without-recursion-and-without-stack/ */ public static void inorderTraversal(TreeNode root){ if(root == null){ return; } Stack stack = new Stack(); TreeNode cur = root; while( true ){ while(cur != null){ // 先添加一个非空节点所有的左孩子到栈 stack.push(cur); cur = cur.left; } if(stack.isEmpty()){ break; } // 因为此时已经没有左孩子了，所以输出栈顶元素 cur = stack.pop(); System.out.print(cur.val + ' '); cur = cur.right; // 准备处理右子树 } }

后序遍历

即：后根遍历

递归：

12345678910111213

/** * 后序遍历递归解法 * （1）如果二叉树为空，空操作 * （2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点 */ public static void postorderTraversalRec(TreeNode root) { if (root == null) { return; } postorderTraversalRec(root.left); postorderTraversalRec(root.right); System.out.print(root.val + ' '); }

非递归

设置两个栈stk, stk2； 将根结点压入第一个栈stk； 弹出stk栈顶的结点，并把该结点压入第二个栈stk2； 将当前结点的左孩子和右孩子先后分别入栈stk； 当所有元素都压入stk2后，依次弹出stk2的栈顶结点，并访问之。

第一个栈的入栈顺序是：根结点，左孩子和右孩子；于是，压入第二个栈的顺序是：根结点，右孩子和左孩子。因此，弹出的顺序就是：左孩子，右孩子和根结点。

123456789101112131415161718192021222324252627282930

/** * 后序遍历迭代解法 * http://www./watch?v=hv-mJUs5mvU * */ public static void postorderTraversal(TreeNode root) { if (root == null) { return; } Stack s = new Stack(); // 第一个stack用于添加node和它的左右孩子 Stack output = new Stack();// 第二个stack用于翻转第一个stack输出 s.push(root); while( !s.isEmpty() ){ // 确保所有元素都被翻转转移到第二个stack TreeNode cur = s.pop(); // 把栈顶元素添加到第二个stack output.push(cur); if(cur.left != null){ // 把栈顶元素的左孩子和右孩子分别添加入第一个stack s.push(cur.left); } if(cur.right != null){ s.push(cur.right); } } while( !output.isEmpty() ){ // 遍历输出第二个stack，即为后序遍历 System.out.print(output.pop().val + ' '); } }

复杂度分析

二叉树遍历的非递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。而使用了栈，空间复杂度为二叉树的高度，故空间复杂度为O(n)。

层次遍历

非递归：

1234567891011121314151617181920212223

/** * 分层遍历二叉树（按层次从上往下，从左往右）迭代 * 相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点 * ，访问，若左子节点或右子节点不为空，将其压入队列 */ public static void levelTraversal(TreeNode root) { if (root == null) { return; } LinkedList queue = new LinkedList(); queue.push(root); while (!queue.isEmpty()) { TreeNode cur = queue.removeFirst(); System.out.print(cur.val + ' '); if (cur.left != null) { queue.add(cur.left); } if (cur.right != null) { queue.add(cur.right); } } }

递归：

1234567891011121314151617181920212223242526272829

/** * 分层遍历二叉树（递归） * 很少有人会用递归去做level traversal * 基本思想是用一个大的ArrayList，里面包含了每一层的ArrayList。 * 大的ArrayList的size和level有关系 * * 这是我目前见到的最好的递归解法！ * http://discuss./questions/49/binary-tree-level-order-traversal#answer-container-2543 */ public static void levelTraversalRec(TreeNode root) { ArrayList> ret = new ArrayList>(); dfs(root, 0, ret); System.out.println(ret); } private static void dfs(TreeNode root, int level, ArrayList> ret){ if(root == null){ return; } // 添加一个新的ArrayList表示新的一层 if(level >= ret.size()){ ret.add(new ArrayList()); } ret.get(level).add(root.val); // 把节点添加到表示那一层的ArrayList里 dfs(root.left, level+1, ret); // 递归处理下一层的左子树和右子树 dfs(root.right, level+1, ret); }

二叉树转为有序的双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

递归：

1234567891011121314151617181920212223242526272829303132

public class Solution { TreeNode phead; //指针 TreeNode realhead; //头指针 public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null) return pRootOfTree; ConvertSub(pRootOfTree); return realhead; } //中序遍历 public void ConvertSub(TreeNode root){ if(root==null) return ; ConvertSub(root.left); if(phead==null){ phead=root; realhead=root; } else{ phead.right=root; root.left=phead; phead=root; } ConvertSub(root.right); }}

非递归：迭代

1234567891011121314151617181920212223242526272829303132333435363738

/** * 将二叉查找树变为有序的双向链表 迭代解法 // * 类似inorder traversal的做法 */ public static TreeNode convertBST2DLL(TreeNode root) { if(root == null){ return null; } Stack stack = new Stack(); TreeNode cur = root; // 指向当前处理节点 TreeNode old = null; // 指向前一个处理的节点 TreeNode head = null; // 链表头 while( true ){ while(cur != null){ // 先添加一个非空节点所有的左孩子到栈 stack.push(cur); cur = cur.left; } if(stack.isEmpty()){ break; } // 因为此时已经没有左孩子了，所以输出栈顶元素 cur = stack.pop(); if(old != null){ old.right = cur; } if(head == null){ // /第一个节点为双向链表头节点 head = cur; } old = cur; // 更新old cur = cur.right; // 准备处理右子树 } return head; }

* 求二叉树第K层的节点个数*

递归

123456789101112131415161718192021222324

/** * 求二叉树第K层的节点个数 递归解法： * （1）如果二叉树为空或者k<1返回0 * （2）如果二叉树不为空并且k==1，返回1 * （3）如果二叉树不为空且k>1，返回root左子树中k-1层的节点个数与root右子树k-1层节点个数之和 * * 求以root为根的k层节点数目 等价于 求以root左孩子为根的k-1层（因为少了root那一层）节点数目 加上 * 以root右孩子为根的k-1层（因为少了root那一层）节点数目 * * 所以遇到树，先把它拆成左子树和右子树，把问题降解 * */ public static int getNodeNumKthLevelRec(TreeNode root, int k) { if (root == null || k < 1) { return 0; } if (k == 1) { return 1; } int numLeft = getNodeNumKthLevelRec(root.left, k - 1); // 求root左子树的k-1层节点数 int numRight = getNodeNumKthLevelRec(root.right, k - 1); // 求root右子树的k-1层节点数 return numLeft + numRight; }

非递归：

12345678910111213141516

/** * 求二叉树第K层的节点个数 迭代解法： * 同getDepth的迭代解法 */ public static int getNodeNumKthLevel(TreeNode root, int k){ if(root == null){ return 0; } Queue queue = new LinkedList(); queue.add(root); int i = 1; int currentLevelNodes = 1; // 当前Level，node的数量 int nextLevelNodes = 0; // 下一层Level，node的数量 while( !queue.isEmpty() && i

求二叉树中叶子结点的个数

递归：

1234567891011121314151617

/** * 求二叉树中叶子节点的个数（递归） */ public static int getNodeNumLeafRec(TreeNode root) { // 当root不存在，返回空 if (root == null) { return 0; } // 当为叶子节点时返回1 if (root.left == null && root.right == null) { return 1; } // 把一个树拆成左子树和右子树之和，原理同上一题 return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right); }

非递归：

12345678910111213141516171819202122232425262728

/** * 求二叉树中叶子节点的个数（迭代） * 还是基于Level order traversal */ public static int getNodeNumLeaf(TreeNode root) { if(root == null){ return 0; } Queue queue = new LinkedList(); queue.add(root); int leafNodes = 0; // 记录上一个Level，node的数量 while( !queue.isEmpty() ){ TreeNode cur = queue.remove(); // 从队头位置移除 if(cur.left != null){ // 如果有左孩子，加到队尾 queue.add(cur.left); } if(cur.right != null){ // 如果有右孩子，加到队尾 queue.add(cur.right); } if(cur.left==null && cur.right==null){ // 叶子节点 leafNodes++; } } return leafNodes; }

判断两棵二叉树是否相同的树

递归：

12345678910111213141516171819202122232425

/** * 判断两棵二叉树是否相同的树。 * 递归解法： * （1）如果两棵二叉树都为空，返回真 * （2）如果两棵二叉树一棵为空，另一棵不为空，返回假 * （3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假 */ public static boolean isSameRec(TreeNode r1, TreeNode r2) { // 如果两棵二叉树都为空，返回真 if (r1 == null && r2 == null) { return true; } // 如果两棵二叉树一棵为空，另一棵不为空，返回假 else if (r1 == null || r2 == null) { return false; } if(r1.val != r2.val){ return false; } boolean leftRes = isSameRec(r1.left, r2.left); // 比较对应左子树 boolean rightRes = isSameRec(r1.right, r2.right); // 比较对应右子树 return leftRes && rightRes; }

非递归：

1234567891011121314151617181920212223242526272829303132333435363738

/** * 判断两棵二叉树是否相同的树（迭代） * 遍历一遍即可，这里用preorder */ public static boolean isSame(TreeNode r1, TreeNode r2) { // 如果两个树都是空树，则返回true if(r1==null && r2==null){ return true; } // 如果有一棵树是空树，另一颗不是，则返回false if(r1==null || r2==null){ return false; } Stack s1 = new Stack(); Stack s2 = new Stack(); s1.push(r1); s2.push(r2); while(!s1.isEmpty() && !s2.isEmpty()){ TreeNode n1 = s1.pop(); TreeNode n2 = s2.pop(); if(n1==null && n2==null){ continue; }else if(n1!=null && n2!=null && n1.val==n2.val){ s1.push(n1.right); s1.push(n1.left); s2.push(n2.right); s2.push(n2.left); }else{ return false; } } return true; }

判断二叉树是不是平衡二叉树

123456789101112131415161718

/** * 判断二叉树是不是平衡二叉树 递归解法： * （1）如果二叉树为空，返回真 * （2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假 */ public static boolean isAVLRec(TreeNode root) { if(root == null){ // 如果二叉树为空，返回真 return true; } // 如果左子树和右子树高度相差大于1，则非平衡二叉树, getDepthRec()是前面实现过的求树高度的方法 if(Math.abs(getDepthRec(root.left) - getDepthRec(root.right)) > 1){ return false; } // 递归判断左子树和右子树是否为平衡二叉树 return isAVLRec(root.left) && isAVLRec(root.right); }

求二叉树的镜像

递归：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354

/** * 求二叉树的镜像 递归解法： * （1）如果二叉树为空，返回空 * （2）如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树 */ // 1. 破坏原来的树，把原来的树改成其镜像 public static TreeNode mirrorRec(TreeNode root) { if (root == null) { return null; } TreeNode left = mirrorRec(root.left); TreeNode right = mirrorRec(root.right); root.left = right; root.right = left; return root; } // 2. 不能破坏原来的树，返回一个新的镜像树 public static TreeNode mirrorCopyRec(TreeNode root){ if(root == null){ return null; } TreeNode newNode = new TreeNode(root.val); newNode.left = mirrorCopyRec(root.right); newNode.right = mirrorCopyRec(root.left); return newNode; } // 3. 判断两个树是否互相镜像 public static boolean isMirrorRec(TreeNode r1, TreeNode r2){ // 如果两个树都是空树，则返回true if(r1==null && r2==null){ return true; } // 如果有一棵树是空树，另一颗不是，则返回false if(r1==null || r2==null){ return false; } // 如果两个树都非空树，则先比较根节点 if(r1.val != r2.val){ return false; } // 递归比较r1的左子树的镜像是不是r2右子树 和 // r1的右子树的镜像是不是r2左子树 return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left); }

非递归：

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455

// 1. 破坏原来的树，把原来的树改成其镜像 public static void mirror(TreeNode root) { if(root == null){ return; } Stack stack = new Stack(); stack.push(root); while( !stack.isEmpty() ){ TreeNode cur = stack.pop(); // 交换左右孩子 TreeNode tmp = cur.right; cur.right = cur.left; cur.left = tmp; if(cur.right != null){ stack.push(cur.right); } if(cur.left != null){ stack.push(cur.left); } } } // 2. 不能破坏原来的树，返回一个新的镜像树 public static TreeNode mirrorCopy(TreeNode root){ if(root == null){ return null; } Stack stack = new Stack(); Stack newStack = new Stack(); stack.push(root); TreeNode newRoot = new TreeNode(root.val); newStack.push(newRoot); while( !stack.isEmpty() ){ TreeNode cur = stack.pop(); TreeNode newCur = newStack.pop(); if(cur.right != null){ stack.push(cur.right); newCur.left = new TreeNode(cur.right.val); newStack.push(newCur.left); } if(cur.left != null){ stack.push(cur.left); newCur.right = new TreeNode(cur.left.val); newStack.push(newCur.right); } } return newRoot; }

求二叉树中节点的最大距离

1234567891011121314151617181920212223242526272829303132333435363738394041424344

/** * 求二叉树中节点的最大距离 即二叉树中相距最远的两个节点之间的距离。 (distance / diameter) * 递归解法： * （1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0 * （2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离， * 要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离， * 同时记录左子树和右子树节点中到根节点的最大距离。 * * http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html * * 计算一个二叉树的最大距离有两个情况: 情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。 情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。 只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离 */ public static Result getMaxDistanceRec(TreeNode root){ if(root == null){ Result empty = new Result(0, -1); // 目的是让调用方 +1 后，把当前的不存在的 (NULL) 子树当成最大深度为 0 return empty; } // 计算出左右子树分别最大距离 Result lmd = getMaxDistanceRec(root.left); Result rmd = getMaxDistanceRec(root.right); Result res = new Result(); res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) + 1; // 当前最大深度 // 取情况A和情况B中较大值 res.maxDistance = Math.max( lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance) ); return res; } private static class Result{ int maxDistance; int maxDepth; public Result() { } public Result(int maxDistance, int maxDepth) { this.maxDistance = maxDistance; this.maxDepth = maxDepth; } }

判断二叉树是不是完全二叉树

非递归迭代

1234567891011121314151617181920212223242526272829303132333435363738394041

/** 14. 判断二叉树是不是完全二叉树（迭代） 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数， 第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。 有如下算法，按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时， 则该节点右子树必须为空，且后面遍历的节点左右子树都必须为空，否则不是完全二叉树。 */ public static boolean isCompleteBinaryTree(TreeNode root){ if(root == null){ return false; } Queue queue = new LinkedList(); queue.add(root); boolean mustHaveNoChild = false; boolean result = true; while( !queue.isEmpty() ){ TreeNode cur = queue.remove(); if(mustHaveNoChild){ // 已经出现了有空子树的节点了，后面出现的必须为叶节点（左右子树都为空） if(cur.left!=null || cur.right!=null){ result = false; break; } } else { if(cur.left!=null && cur.right!=null){ // 如果左子树和右子树都非空，则继续遍历 queue.add(cur.left); queue.add(cur.right); }else if(cur.left!=null && cur.right==null){ // 如果左子树非空但右子树为空，说明已经出现空节点，之后必须都为空子树 mustHaveNoChild = true; queue.add(cur.left); }else if(cur.left==null && cur.right!=null){ // 如果左子树为空但右子树非空，说明这棵树已经不是完全二叉完全树！ result = false; break; }else{ // 如果左右子树都为空，则后面的必须也都为空子树 mustHaveNoChild = true; } } } return result; }

非递归：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354

/** * 14. 判断二叉树是不是完全二叉树（递归） * http:///questions/1442674/how-to-determine-whether-a-binary-tree-is-complete * */ public static boolean isCompleteBinaryTreeRec(TreeNode root){ // Pair notComplete = new Pair(-1, false); // return !isCompleteBinaryTreeSubRec(root).equalsTo(notComplete); return isCompleteBinaryTreeSubRec(root).height != -1; } // 递归判断是否满树（完美） public static boolean isPerfectBinaryTreeRec(TreeNode root){ return isCompleteBinaryTreeSubRec(root).isFull; } // 递归，要创建一个Pair class来保存树的高度和是否已满的信息 public static Pair isCompleteBinaryTreeSubRec(TreeNode root){ if(root == null){ return new Pair(0, true); } Pair left = isCompleteBinaryTreeSubRec(root.left); Pair right = isCompleteBinaryTreeSubRec(root.right); // 左树满节点，而且左右树相同高度，则是唯一可能形成满树（若右树也是满节点）的情况 if(left.isFull && left.height==right.height){ return new Pair(1+left.height, right.isFull); } // 左树非满，但右树是满节点，且左树高度比右树高一 // 注意到如果其左树为非完全树，则它的高度已经被设置成-1， // 因此不可能满足第二个条件！ if(right.isFull && left.height==right.height+1){ return new Pair(1+left.height, false); } // 其他情况都是非完全树，直接设置高度为-1 return new Pair(-1, false); } private static class Pair{ int height; // 树的高度 boolean isFull; // 是否是个满树 public Pair(int height, boolean isFull) { this.height = height; this.isFull = isFull; } public boolean equalsTo(Pair obj){ return this.height==obj.height && this.isFull==obj.isFull; } }

二叉树转堆

问题：给定一个存储于一个无序的二叉树中的整数集合。使用数组排序算法将这个树转化为一个堆，这个堆使用一个平衡二叉树作为底层的数据结构。