226.翻转二叉树
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
https://www.bilibili.com/video/BV1sP4y1f7q7思路：前序遍历，交换遍历到的节点左右节点的地址。注意如果用中序遍历，则是先翻转遍历到的节点的左子树，再翻转遍历到的节点的左右节点地址，此时原来的左子树经交换地址已经变为右子树，所以不能再翻转右子树，而是再翻转左子树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//前序
public TreeNode invertTree(TreeNode root) {
invert(root);
return root;
}
public void invert(TreeNode root) {
if (root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invert(root.left);
invert(root.right);
}
}101. 对称二叉树
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
思路： 利用后序先看左右子树是否翻转一样，左节点的右子树翻转过去变成右节点的左子树，所以在递归过程中，左节点的右子树与右节点的左子树比较，同理左节点的左子树与右节点的右子树比较。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
public boolean isSymmetric(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;
}
//左右节点值一样，递归看左节点的左子树和右节点的右子树翻转是否一样
boolean symmetric1 = isSymmetric(left.left, right.right);
//同理
boolean symmetric2 = isSymmetric(left.right, right.left);
return symmetric1 && symmetric2;
}
}104.二叉树的最大深度
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
思路： 深度为节点到头节点的距离，高度为节点到叶子节点的距离。求深度一般用前序，求高度一般用后序。而最大深度又是最大高度，所以用后序求最大高度。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
return getHight(root);
}
public int getHight(TreeNode node) {
if (node == null) {
return 0;
}
int lhight = getHight(node.left);
int rhight = getHight(node.right);
return Math.max(lhight, rhight) + 1;
}
}111.二叉树的最小深度
题目链接：. - 力扣（LeetCode）
文章链接：代码随想录
思路：方法一：用后序求跟节点到叶子节点的高度来求根节点到叶子节点的最短路径。
方法二：用层序遍历，利用了队列，如果队列弹出第一个左右子树均为空，那么这个就是叶子节点，则直接返回该节点所在层。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
return getHight(root);
}
public int getHight(TreeNode node) {
if (node == null) {
return 0;
}
int lhight = getHight(node.left);
int rhight = getHight(node.right);
if (node.left == null && node.right != null) {
return rhight + 1;
}
if (node.left != null && node.right == null) {
return lhight + 1;
}
return Math.min(lhight, rhight) + 1;
}
}标签：right,TreeNode,val,随想录,二叉树,深度,LeetCode,left From： https://blog.csdn.net/qq_73932604/article/details/143349326