云南网站制作案例,网站策划建设阶段的推广,购物网站建设教程,做网站防护的网站110.平衡二叉树 #xff08;优先掌握递归#xff09;后序遍历 左右中 class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) ! -1;}//递归三部曲 确定方法的参数与返回值private int getHeight(TreeNode root){//明确终止条件if(root null){r… 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 ListString binaryTreePaths(TreeNode root) {ListString res new ArrayList(); //最终结果if(root null){return res;}//结果中的路径 ListInteger paths new ArrayList();traversal(root,paths,res);return res;}private void traversal(TreeNode root,ListInteger paths,ListString 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;}
}
