剑指Offer之Java算法习题精讲二叉树与斐波那契函数

题目一

解法

class Solution {
  public int fib(int n) {
      int[] arr = new int[31];
      arr[0] = 0;
      arr[1] = 1;
      for(int i = 2;i<=n;i++){
          arr[i] = arr[i-2]+arr[i-1];
      }
      return arr[n];
  }
}

 

题目二

 解法

/**
* 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 {
  int index = 0;
  int ans = 0;
  public int kthSmallest(TreeNode root, int k) {
      method(root,k);
      return ans;
  }
  void method(TreeNode root, int k){
      if(root==null) return;
      method(root.left,k);
      index++;
      if(index==k){
          ans = root.val;
          return;
      }
      method(root.right,k);
  }
}

 

题目三

解法

/**
* 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) {
      if (root == null) {
          return 0;
      }
      if (root.left == null && root.right == null) {
          return 1;
      }
      int min_depth = Integer.MAX_VALUE;
      if (root.left != null) {
          min_depth = Math.min(minDepth(root.left), min_depth);
      }
      if (root.right != null) {
          min_depth = Math.min(minDepth(root.right), min_depth);
      }
      return min_depth + 1;
  }
}

到此这篇关于剑指Offer之Java算法习题精讲二叉树与斐波那契函数的文章就介绍到这了,更多相关Java二叉树与斐波那契函数内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

原文链接：https://blog.csdn.net/wai_58934/article/details/123484258

查看更多关于剑指Offer之Java算法习题精讲二叉树与斐波那契函数的详细内容...