Java日记2018-05-19

第一题 二叉搜索树的第 K 个结点
二叉搜素树的中序遍历访问队列，自然的满足升序排序的条件，中序遍历二叉搜索树找到第k大的节点
采用递归的方法，以下图为例

image.png

中序遍历找到最左端的中间节点2，计数器+1，然后退回根节点变成3，计数器+1，找右树4，计数器+1，此时找到第三大值。
注意计数器单独存放，如果放到inorder里，那么递归时候会被充值，导致计算出错

public class KthNode {
    public static BinaryTreeNode findknode(BinaryTreeNode root, int k) {
        inorder(root, k);
        return ret;
    }

    private static int cnt = 0;
    private static BinaryTreeNode ret;

    public static void inorder(BinaryTreeNode root, int k) {
        if (root == null || cnt >= k)
            return;
        System.out.println(root.val+" "+cnt);
        inorder(root.left, k);
        cnt++;
        if (cnt == k)
            ret = root;
        System.out.println("cnt rit:"+root.val+" "+cnt);
        inorder(root.right, k);

    }

    public static void main(String[] args) {
        BinaryTreeNode n1 = new BinaryTreeNode(5);
        BinaryTreeNode n2 = new BinaryTreeNode(3);
        BinaryTreeNode n3 = new BinaryTreeNode(7);
        BinaryTreeNode n4 = new BinaryTreeNode(2);
        BinaryTreeNode n5 = new BinaryTreeNode(4);
        BinaryTreeNode n6 = new BinaryTreeNode(6);
        BinaryTreeNode n7 = new BinaryTreeNode(8);
        n1.left = n2;
        n1.right = n3;

        n2.left = n4;
        n2.right = n5;

        n3.left = n6;
        n3.right = n7;
        System.out.println(findknode(n1, 3));
    }

}

第二题 二叉树的深度 、
递归……

public int TreeDepth(TreeNode root) {
    return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
}

第三题 平衡二叉树
平衡二叉树左右子树高度差不超过 1。

private boolean isBalanced = true;

public boolean IsBalanced_Solution(TreeNode root) {
    height(root);
    return isBalanced;
}

private int height(TreeNode root) {
    if (root == null)
        return 0;
    int left = height(root.left);
    int right = height(root.right);
    if (Math.abs(left - right) > 1)
        isBalanced = false;
    return 1 + Math.max(left, right);
}

第四题 数组中只出现一次的数字

参考 https://blog.csdn.net/jsqfengbao/article/details/47402969

举个例子，加入我们输入的数字是｛2，4，3，6，3，2，5，5｝。当我们依次对数组中的每一个数字做异或（相同为0不同为1）运算之后，得到的结果用二进制表示为0010.异或得到的结果中的倒数第二位是1，也就是说两个不相同数字的倒数第二位不一致，根据这个划分，如果数字与0010相与等于0（两位同时为“1”，结果才为“1”，否则为0），即数字的倒数第二位不相同。

根据倒数第二位是否一致划分两组进行异或运算，因为 2 2 3这样的数字异或等于3，很显然两组分别异或后能算出只出现一次结果。

将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。

diff &= -diff 得到出 diff 最右侧不为 0 的位

public class FindNumsAppearOnce {
    public static void FindNumsAppearOnce(int[] nums, int num1, int num2) {
        int diff = 0;
        for (int num : nums)
            diff ^= num;
        // 得到最右一位
        System.out.println(diff);
        diff &= -diff;
        
        for (int num : nums) {
            if ((num & diff) == 0) {
                System.out.println("num1 is: "+num);
                num1 ^= num;
            }
            else
                num2 ^= num;
        }
        System.out.println(num1+num1);
    }
    public static void main(String[] args) {
        int[] arr={6,2,4,3,3,2,5,5,8,9,8,9};
        int[] arr2=new int[16];
        int[] arr3 = new int[16];
        FindNumsAppearOnce(arr,0,0);
        int te = 2^3;
        System.out.println("test"+te);
    }

}

第五题 和为 S 的两个数字

输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得他们的和正好是 S，如果有多对数字的和等于 S，输出两个数的乘积最小的。

使用双指针，一个指针指向元素较小的值，一个指针指向元素较大的值。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

• 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
• 如果 sum > target，移动较大的元素，使 sum 变小一些；
• 如果 sum < target，移动较小的元素，使 sum 变大一些。

public String FindFunction(int[] numarray,int k){  
        if(numarray == null)  
            return null;  
          
        int i = 0;  
        int j = numarray.length-1;  
        int sum = 0;  
          
        while(sum != k){  
            sum = numarray[i] + numarray[j];  
            if(sum > k){  
                j--;  
            }  
            if(sum < k){  
                i++;  
            }  
        }  
        return numarray[i] + "和" + numarray[j];  
    }