代码随想录算法训练营|226.翻转二叉树 、 101. 对称二叉树、 104.二叉树的最大深度、 111.二叉树的最小深度

226.翻转二叉树

题目

 参考文章

思路：这里的翻转二叉树其实就是考对前中后序遍历的理解，这道题用前序和后序是比较方便的，这里我用了前序遍历的方式解题。首先交换当前节点的左右子节点，然后递归当前节点的左右子节点（相当于到了子节点还是做同样的操作），知道所有节点遍历完了，就完成了翻转，返回root即可

代码：

class Solution {public TreeNode invertTree(TreeNode root) {if(root==null){return root;}swap(root);invertTree(root.left);invertTree(root.right);return root;}public void swap(TreeNode node){TreeNode temp=node.left;node.left=node.right;node.right=temp;}
}

101. 对称二叉树

题目

参考文章

思路：这里是比较二叉树内外侧的值，才是这题的正解。这里只能用类似后续遍历的方式来进行，因为要先比较内外侧值，再把他们比较的Boolean值，看看是否都为true，若全部都是true，就是对称二叉树

代码：

class Solution {public boolean isSymmetric(TreeNode root) {return compare(root.left,root.right);}private boolean compare(TreeNode left, TreeNode right) {if (left == null && right != null) {return false;}if (left != null && right == null) {return false;}if (left == null && right == null) {return true;}if (left.val != right.val) {return false;}// 外侧boolean compareOutside = compare(left.left, right.right);// 内侧boolean compareInside = compare(left.right, right.left);return compareOutside && compareInside;}
}

104.二叉树的最大深度

题目

参考文章

思路：这题的就是区分高度和深度的题目，不过也可以用求高度的方法求得（即求根节点的高度即可，这个就是用到了后序遍历），求深度就是从根节点开始遍历，直到找到最深的叶子节点即可（相当于前序遍历），这里用前序遍历的方式解题

代码：

class Solution {//最大深度int maxnum = 0;public int maxDepth(TreeNode root) {ans(root,0);return maxnum;}void ans(TreeNode tr,int tmp){if(tr==null){return;}tmp++;maxnum=maxnum<tmp?tmp:maxnum;ans(tr.left,tmp);ans(tr.right,tmp);tmp--;}
}

111.二叉树的最小深度

题目

参考文章

思路：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。

这里会陷入一个误区，以为和上面一题最大深度思路差不多，只是取了最小值。这里只是取最小值是不正确的，因为一旦有一个节点的左或右节点出现了空，此时这个位置成为了最小值，但是不符合题意的，题意是到叶子节点的最小深度。所以要做判断，当遍历了左右深度之后，判断左节点是否空，为空则直接返回1+rightDepth ，再判断右节点是否为空，为空则返回1+leftDepth；若左右节点都不为空，才返回他们之间的最小值

代码：

class Solution {public int minDepth(TreeNode root) {if(root==null){return 0;}int leftDepth=minDepth(root.left);int rightDepth=minDepth(root.right);if(root.left==null){return 1+rightDepth;}if(root.right==null){return 1+leftDepth;}return 1+Math.min(rightDepth,leftDepth);}
}