2019.5.31今日算法题

给定一棵二叉搜索树，请找出其中的第k小的结点。例如（5，3，7，2，4，6，8）中第三小结点的值为4。

技术点： 树

思路：二叉搜索树的中序遍历结果正好是从小到大排序好的，按照中序遍历顺序找第k个节点

参考代码：

//节点类TreeNode同上
public class Solution {
    int index = 0; //计数器
    TreeNode KthNode(TreeNode root, int k){
        if(root != null){
            TreeNode node = KthNode(root.left,k);
            if(node != null) return node;//注意需要判断是否为空，否则如果找到符合要求的节点只能返回到上一层，而不能返回到顶层，使得输出结果为null
            index ++;
            if(index == k) return root;
            node = KthNode(root.right,k);
            if(node != null) return node;//理由同上
        }
        return null;
    }
}

---

Q：输入一棵二叉树，判断该二叉树是否是平衡二叉树。

技术点：树

思路：从下往上遍历，如果子树是平衡二叉树，则返回子树的高度，反之直接停止遍历，这样至多只对每个结点访问一次

参考代码：

//节点类TreeNode同上
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }
    private int getDepth(TreeNode root) {
        if (root == null) return 0;
        int left = getDepth(root.left);
        if (left == -1) return -1;
        int right = getDepth(root.right);
        if (right == -1) return -1;
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}

---

 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

技术点： 递归和循环

思路：对于第n个台阶来说，只能从n-1或n-2的台阶跳上来，因此跳到n阶的跳法=跳到n-1阶的方案+跳到n-2阶的方案，即F(n) = F(n-1) + F(n-2)，是个斐波拉契数序列

参考代码：

//递归法
public class Solution {
    public int JumpFloor(int target) {
        if (target <= 2) {
            return target;
        } else {
            return  JumpFloor(target-1)+JumpFloor(target-2);
        }
    }
}
//迭代法
public class Solution {
    public int JumpFloor(int target) {
        if (target <= 2) {
            return target;
        } 
        int f1=1;
        int f2=2;
        int f=0;
        for(int i=3;i<=target;i++){
            f=f1+f2;
            f1=f2;
            f2=f;
        }
        return f;
    }
}

    
                             

 

---

                                                                                                                                 by .k

 

关注"编程v",每一天涨一点

STAY HUNGRY & STAY FOOLISH