代码随想录算法训练营第十七天二叉树 java : . 110.平衡二叉树 257.二叉树的所有路径 404.左叶子之和

前言

选择一个简单的理念矢志不渝地去执行Take one simple idea and take it seriously

递归三部曲

• 确定递归函数的参数和返回值
• 确定终止条件
• 确定单层递归的逻辑

Leetcode 110.平衡二叉树

题目讲解

思路

• 深度 指从根节点到该节点的最长简单路径边的条数。
• 高度 指从该节点到叶子节点的最长简单路径边的条数。

这道题主要用到高度 需要用后序算法

节点的左右子树的高度小于等于1

如果左右子树高度差大于一 就返回 return -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) {
      return getHeight(root)!=-1;   //传回的二叉树是二叉平衡树
    }
    public 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;
    }

}

Leetcode 257. 二叉树的所有路径

题目讲解

明天需要再看一遍

这道题涉及到了回溯

题解里 讲到用了递归必然涉及到回溯

这里用的是前序遍历 因为中 左右 从父结点到左右两个孩子 在返回的时候就需要用到回溯减回去

/**
 * 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) {
        List<String> res =new ArrayList<>();
        if( res== null)
        {
            return res;
        }
        List<Integer> paths =new ArrayList<>();
        traveler(root,paths,res);
        return res;
    }
   public void traveler(TreeNode root,List<Integer>paths,List<String>res){
    //中
       paths.add(root.val);
    if( root.left ==null && root.right ==null)
    { 
       
       StringBuilder sb =new StringBuilder();
       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)
    {
          traveler(root.left,paths,res);
          paths.remove(paths.size()-1);
    }
    //右边
    if(root.right!=null)
    {
         traveler(root.right,paths,res);
         paths.remove(paths.size()-1);
    }


}}

Leetcode 404.左叶子之和

题目讲解

nxp,java里居然没有value 只能用val

/**
 * 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) {
      if(root == null) return 0;
      int leftsum = sumOfLeftLeaves(root.left);
      int rightsum = sumOfLeftLeaves(root.right);
      int midsum =0;
      if(root.left!=null && root.left.left ==null&& root.left.right ==null)
      {
         midsum = root.left.val;
      }
      int sum = leftsum+rightsum+midsum;
      return sum;

    }
}

总结

马上打算开启 复习数据库和计网 了 今天触及到了 回溯算法 很兴奋