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

226.翻转二叉树

思路

使用递归将子树的左右子树翻转

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

01. 对称二叉树

思路

使用递归判断左右子树是否对称，这里使用后序遍历且返回boolean值，只有左子树是否对称的结果，右子树的结果都为true,则当前根节点为true

class Solution {public boolean isSymmetric(TreeNode root) {return compare(root.left, root.right);}public boolean compare(TreeNode left, TreeNode right){if(left == null && right != null){return false;}else if(left != null && right == null){return false;}else if(left == null && right == null){return true;}else if(left.val != right.val){return false;}//这里注意别比较相等时候，弄清楚结束边界// else if(left.val == right.val){//     return true;// }boolean a =  compare(left.right, right.left);boolean b =  compare(left.left, right.right);return a && b;}
}

104.二叉树的最大深度

思路

• 二叉树的最大深度就是根节点的最大高度
• 递归函数传入两个参数root和deepth，deepth用来更新当前高度。
• 每次递归返回当前节点的最大高度，取左子树和右子树的高度最大值加一（1+Math.max(left,right)）

class Solution {public int maxDepth(TreeNode root) {int deep = 0;return getDepth(root, deep);}public int getDepth(TreeNode root, int deep) {if(root == null){return 0;}int left = getDepth(root.left,deep);int right = getDepth(root.right, deep);return 1+Math.max(left,right);}
}

111.二叉树的最小深度

class Solution {/*** 递归法，相比求MaxDepth要复杂点* 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量*/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 rightDepth + 1;}if (root.right == null) {return leftDepth + 1;}// 左右结点都不为nullreturn Math.min(leftDepth, rightDepth) + 1;}
}