day17-二叉树part04

2024-04-04 00:04

文章标签 二叉树 part04 day17

本文主要是介绍day17-二叉树part04，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

110.平衡二叉树（优先掌握递归）后序遍历左右中

class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}//递归三部曲 确定方法的参数与返回值private int getHeight(TreeNode root){//明确终止条件if(root == null){return 0;}//确认单层递归逻辑 //后序遍历 左右中int leftHeight = getHeight(root.left);if(leftHeight == -1){return -1;}int rightHeight = getHeight(root.right);if(rightHeight == -1){return -1;}//比较左右子树高度差 如果大于一直接返回不是平衡二叉树if(Math.abs(leftHeight - rightHeight) > 1){return -1;}return Math.max(leftHeight,rightHeight) + 1;}
}

257. 二叉树的所有路径（优先掌握递归）前序遍历根左右

class Solution {//根节点到叶子节点的所有路径 前序遍历先获取根节点public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();   //最终结果if(root == null){return res;}//结果中的路径 List<Integer> paths = new ArrayList<>();traversal(root,paths,res);return res;}private void traversal(TreeNode root,List<Integer> paths,List<String> res){paths.add(root.val);//终止条件if(root.left == null && root.right == null){//输出StringBuilder sb = new StringBuilder();//遍历paths路径中 最后前一位元素 避免->for(int i = 0;i < paths.size()-1;i++){sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() -1 )); //记录最后一个路径res.add(sb.toString()); //收集一条路径return;}//单层递归逻辑//左if(root.left != null){traversal(root.left,paths,res);//下一个节点完成  回溯paths.remove(paths.size() -1); }//右if(root.right != null){traversal(root.right,paths,res);paths.remove(paths.size() -1);}}
}

404.左叶子之和（优先掌握递归）

左叶子定义:节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

class Solution {//后序遍历 左右中public int sumOfLeftLeaves(TreeNode root) {if(root == null){return 0;}if(root.left == null && root.right == null) return 0;int leftVaule = sumOfLeftLeaves(root.left);         //左if(root.left != null && root.left.left == null && root.left.right == null){ // 左子树就是一个左叶子的情况leftVaule = root.left.val;}int rightValue = sumOfLeftLeaves(root.right);       //右int sum =leftVaule + rightValue;                    //中return sum;}
}

这篇关于day17-二叉树part04的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！