二叉树的基础练习（Java） Java

题目：

1. 二叉树的前序遍历 2. 二叉树中序遍历 3. 二叉树的后序遍历 4. 检查两颗树是否相同 5. 另一颗树的子树 6. 二叉树最大深度 7. 判断一颗二叉树是否是平衡二叉树 8. 对称二叉树

【二叉树的基础练习（Java）】代码：

import java.util.ArrayList; import java.util.List; class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int x) { val = x; } }public class Test { //前序遍历 public List preorderTraversal(TreeNode root) { List list = new ArrayList<>(); // 空树返回一个空的 List (元素个数为 0, 但是不是 null) if(root == null){ return list; } // 访问根节点, 此处的访问操作, 把元素 add 到 List 中 list.add(root.val); // 递归遍历左子树, 把左子树的遍历结果加入到 List 中 list.addAll(preorderTraversal(root.left)); // 递归遍历右子树, 把右子树的遍历结果加到 List 中 list.addAll(preorderTraversal(root.right)); return list; } //中序遍历 public List inorderTraversal(TreeNode root) { List list = new ArrayList<>(); // 空树返回一个空的 List (元素个数为 0, 但是不是 null) if(root == null){ return list; } // 递归遍历左子树, 把左子树的遍历结果加入到 List 中 list.addAll(inorderTraversal(root.left)); // 访问根节点, 此处的访问操作, 把元素 add 到 List 中 list.add(root.val); // 递归遍历右子树, 把右子树的遍历结果加到 List 中 list.addAll(inorderTraversal(root.right)); return list; } //后序遍历 public List postorderTraversal(TreeNode root) { List list = new ArrayList<>(); if(root == null){ return list; } list.addAll(postorderTraversal(root.left)); list.addAll(postorderTraversal(root.right)); list.add(root.val); return list; }//检查两颗二叉树是否相同 public boolean isSameTree(TreeNode p, TreeNode q){ //可以分为四种情况 //1、p，q都为null； //2、p为null，q不为null； //3、q为null，p不为null； //4、p，q都不为null//两个树若为空树，那么认为这两个树相同 if(p == null && q == null){ return true; } //两个树若一个为空，一个不为空，肯定不同 //if((p == null && q != null) || (p != null && q == null)) if(p == null || q == null){ return false; } //两个树都不为空，若根的值不同，那么两个树不同 if(p.val != q.val){ return false; } //否则，递归遍历两个树的左右子树 return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); }//是否是另一棵树的子树 public boolean isSubtree(TreeNode s, TreeNode t) { if(s == null && t == null){ return true; } if(s == null || t == null){ return false; } boolean ret = true; if(s.val == t.val){ ret = isSameTree(s,t); } return ret || isSubtree(s.left,t) || isSubtree(s.right,t); } //二叉树的最大深度 public int maxDepth(TreeNode root) { //若二叉树为空，深度为0 if(root == null){ return 0; } //若二叉树的左右子树都为空，深度为1 if(root.left == null && root.right == null){ return 1; } //若二叉树左右子树都不为空，递归判断左右子树的深度 int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); return 1+(leftDepth>rightDepth?leftDepth:rightDepth); }//判断一个二叉树，是否是平衡二叉树 // 平衡二叉树，左右子树的深度绝对值不大于于1 public boolean isBalanced(TreeNode root) { //若二叉树为空，那么是一个平衡二叉树 if(root == null){ return true; } //若二叉树没有子树，那么也是一个平衡二叉树 if(root.left == null && root.right == null){ return true; } //若二叉树左右子树都不为空，递归判断左右子树的深度 int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); //若左右子树的深度绝对不小于1，那么一定不是一个平衡二叉树 if(leftDepth - rightDepth >1 || leftDepth - rightDepth < -1){ return false; } //否则，递归判断当前结点是否为平衡二叉树 return isBalanced(root.left) && isBalanced(root.right); }//判断是否是对称二叉树 public boolean isSymmetric(TreeNode root) { //空树一定对称 if(root == null){ return true; } //判断左右子树是否成对称 return isMirrorTree(root.left,root.right); } public boolean isMirrorTree(TreeNode p, TreeNode q){ //若两个子树为空，一定对称 if(p == null && q == null){ return true; } //若两个子树，一个为空，另一个不为空，一定不对称 if(p == null || q == null){ return false; } //若两个子树根节点不同，一定不对称 if(p.val != q.val){ return false; } return isMirrorTree(p.left,q.right) && isMirrorTree(p.right,q.left); }}