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

剑指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.minhttp://(minDepth(root.right), min_depth);

}

return min_depth + 1;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。