110.平衡二叉树
题目链接：. - 力扣（LeetCode）
文章链接：代码随想录
https://www.bilibili.com/video/BV1Ug411S7my思路：后序先求左右子树高度，再比较高度差，超过1就不是平衡二叉树。
/**
* 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 isBalanced(TreeNode root) {
if (getHight(root)==-1){
return false;
}
return true;
}
public int getHight(TreeNode root) {
if (root == null) {
return 0;
}
int lhight = getHight(root.left);
int rhight = getHight(root.right);
if (lhight == -1 || rhight == -1) {
return -1;
}
if (Math.abs(lhight - rhight) > 1) {
return -1;
}
return Math.max(lhight, rhight) + 1;
}
}257. 二叉树的所有路径
题目链接：. - 力扣（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 List<String> binaryTreePaths(TreeNode root) {
ArrayList<Integer> path = new ArrayList<>();
ArrayList<String> result = new ArrayList<>();
getPath(root,path,result);
return result;
}
public void getPath(TreeNode root, ArrayList<Integer> path, ArrayList<String> result) {
path.add(root.val);
if (root.left == null && root.right == null) {
//StringJoiner stringJoiner = new StringJoiner("->");
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < path.size(); i++) {
if (i == path.size() - 1) {
stringBuilder.append(path.get(i));
break;
}
stringBuilder.append(path.get(i)).append("->");
}
result.add(stringBuilder.toString());
return;
}
if (root.left != null) {
getPath(root.left, path, result);
path.remove(path.size() - 1);
}
if (root.right != null) {
getPath(root.right, path, result);
path.remove(path.size() - 1);
}
}
}404.左叶子之和
题目链接：. - 力扣（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 sumOfLeftLeaves(TreeNode root) {
return getSumOfLeftLeaves(root);
}
public int getSumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 0;
}
int lsum = getSumOfLeftLeaves(root.left);
if (root.left != null && root.left.left == null && root.left.right == null) {
lsum = root.left.val;
}
int rsum = getSumOfLeftLeaves(root.right);
return lsum + rsum;
}
}222.完全二叉树的节点个数
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
思路：正常二叉树是后序先求左右子树的节点数，再加1。但是因为完全二叉树的特性，我们可以先判断是否为满二叉树，如果是则直接得出节点数为2的数的高度次方-1，否则再按正常方法求节点数。
/**
* 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 countNodes(TreeNode root) {
return getCountNode(root);
}
public int getCountNode(TreeNode root) {
if (root == null) {
return 0;
}
int ldept = 0, rdept = 0;
TreeNode temp = root;
while (temp != null) {
ldept++;
temp = temp.left;
}
temp = root;
while (temp != null) {
rdept++;
temp = temp.right;
}
if (ldept == rdept) {
return (int) (Math.pow(2, ldept) - 1);
}
int lcount = getCountNode(root.left);
int rcount = getCountNode(root.right);
return lcount + rcount + 1;
}
}标签：TreeNode,val,随想录,二叉树,left,root,LeetCode,第十三天 From： https://blog.csdn.net/qq_73932604/article/details/143375639