Java数据结构第十四期：走进二叉树的奇妙世界(三)

专栏：数据结构(Java版)

个人主页：手握风云

一、二叉树OJ练习题

1.1. 相同的树

1.2. 另一棵树的子树

1.3. 翻转二叉树

1.4. 平衡二叉树

1.5. 对称二叉树

一、二叉树OJ练习题

1.1. 相同的树

判断两棵树是否相同，我们是否只能遍历一遍看结果？看下面的三棵二叉树，上面的树存储的值相同，结构也相同；中间的树存储的值相同，但结构不同；下面的树存储的值不相同。所以我们只遍历一遍看结果不可以。

我们以相同的方式来遍历两棵二叉树。要判断两棵树结构相同，要么结点同时为空，要么同时不为空。当两个结点都不为空，再去判断结点所存储的值是否相同。先定义两个引用p、q，然后判断根结点是否相同。我们以下图为例，根结点相同、左子树相同且右子树也相同再去判断值相同。如果一个为空，另一个不为空，则结构不同；如果两个引用都不为空，但值不同，也返回false。

完整代码：

class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode(){}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}/*** 时间复杂度O(min(m.n))* m为p这棵树的结点，n为q这棵树的结点* 结点小的最先遍历完*/
public class Solution {public boolean isSameTree(TreeNode p, TreeNode q){if((p != null && q == null) || (p == null && q!= null)){return false;}//上面的if语句不生效，代表要么都为空，要么都不为空if(p == null && q == null){return true;}//只剩下都不为空的情况，再判断值是否相同if(p.val != q.val){return false;}return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}

public class Test {public static void main(String[] args) {Solution solution = new Solution();TreeNode Tree1 = new TreeNode(1,new TreeNode(2),null);TreeNode Tree2 = new TreeNode(1,null,new TreeNode(2));System.out.println(solution.isSameTree(Tree1,Tree2));TreeNode Tree3 = new TreeNode(1,new TreeNode(2),new TreeNode(3));TreeNode Tree4 = new TreeNode(1,new TreeNode(2),new TreeNode(3));System.out.println(solution.isSameTree(Tree3,Tree4));TreeNode Tree5 = new TreeNode(1,new TreeNode(2),new TreeNode(1));TreeNode Tree6 = new TreeNode(1,new TreeNode(1),new TreeNode(2));System.out.println(solution.isSameTree(Tree5,Tree6));}
}

1.2. 另一棵树的子树

一棵树的本身就是它的子树，所以我们要首先判断两棵树是否相同，再去判断subRoot是不是等于root的左子树还是右子树，判断我们可以依照上面讲过的是否是相同的树来判断。

完整代码：

class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(){}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot){if(root == null) {return false;}if(isSameTree(root,subRoot)){return true;}if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right,subRoot)){return true;}return false;}public boolean isSameTree(TreeNode p, TreeNode q) {if((p != null && q == null) || (p == null && q!= null)){return false;}//上面的if语句不生效，代表要么都为空，要么都不为空if(p == null && q == null){return true;}//只剩下都不为空的情况，再判断值是否相同if(p.val != q.val){return false;}return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}

public class Test {public static void main(String[] args) {Solution solution = new Solution();TreeNode root = new TreeNode(3,new TreeNode(4),new TreeNode(5));root.left.left = new TreeNode(1);root.left.right = new TreeNode(2);TreeNode SubRoot = new TreeNode(4,new TreeNode(1),new TreeNode(2));System.out.println(solution.isSubtree(root, SubRoot));}
}

1.3. 翻转二叉树

翻转就是把每一个结点的左右孩子都进行交换（如下图所示）。下图可能有一些抽象，我们可以从内存上对二叉树进行一个翻转。只要root不为空，就对左右结点进行交换。当root遍历完整棵二叉树，就可以进行翻转。

完整代码：

class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(){}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public TreeNode invertTree(TreeNode root){if(root == null){return null;}if(root.left == null && root.right == null){return root;}TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;}public void PrevOrder(TreeNode root){if(root == null){return;}System.out.print(root.val+" ");PrevOrder(root.left);PrevOrder(root.right);}
}

public class Test {public static void main(String[] args) {Solution solution = new Solution();TreeNode root = new TreeNode(4,new TreeNode(2),new TreeNode(7));root.left.left = new TreeNode(1);root.left.right = new TreeNode(3);root.right.left = new TreeNode(6);root.right.right = new TreeNode(9);System.out.print("翻转之前：");solution.PrevOrder(root);System.out.println();solution.invertTree(root);System.out.print("翻转之后：");solution.PrevOrder(root);}
}

1.4. 平衡二叉树

平衡二叉树是指该树所有节点的左右子树的高度相差不超过1。很明显这道题是涉及到求二叉树深度的问题。实现的逻辑也非常简单：求出每棵子树的高度，如果左子树的高度与右子树的高度之差小于等于1，则是平衡二叉树。我们可以调用之前求二叉树的最大深度的方法来求高度。但还存在一种反例（如下图所示）。下面这棵二叉树就不是平衡二叉树，因为9这个的结点的左右子树高度差为2。那么我们就不能只求一次高度，还需要重复计算高度，那么此时的时间复杂度也会随着增大， $O(n^{2})$ 。

class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(){}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public boolean isBalanced(TreeNode root){if(root == null){return true;}int leftHeight = MaxDepth(root.left);int rightHeight = MaxDepth(root.right);return Math.abs(leftHeight - rightHeight) <= 1&& isBalanced(root.left)&& isBalanced(root.right);}public int MaxDepth(TreeNode root){if(root == null){return 0;}int leftH = MaxDepth(root.left);int rightH = MaxDepth(root.right);return Math.max(leftH,rightH)+1;}
}

public class Test {public static void main(String[] args) {Solution solution = new Solution();TreeNode root = new TreeNode(3,new TreeNode(9),new TreeNode(20));root.right.left = new TreeNode(15);root.right.right = new TreeNode(7);System.out.println(solution.isBalanced(root));}
}

1.5. 对称二叉树

要判断二叉树是否是对称的，也就是判断左右子树是否是对称的（如下图所示）。root.left与root.right是否是对称的，再判断下面的子结点是否对称，也就是递归的条件。

class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(){}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public boolean isSymmetric(TreeNode root){if(root == null){return true;}return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){if(leftTree == null && rightTree != null || leftTree != null && rightTree == null){return false;}if(leftTree == null && rightTree == null){return true;}if(leftTree.val != rightTree.val){return false;}return isSymmetricChild(leftTree.left,rightTree.right)&& isSymmetricChild(leftTree.right,rightTree.left);}
}

public class Test {public static void main(String[] args) {Solution solution = new Solution();TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(2));root.left.left = new TreeNode(3);root.left.right = new TreeNode(4);root.right.left = new TreeNode(4);root.right.right = new TreeNode(3);System.out.println(solution.isSymmetric(root));}
}