import java.util.ArrayList;
import java.util.List;

//class Solution {
//    public List<List<Integer>> generate(int numRows) {
//        List<List<Integer>> ret = new ArrayList<>();
//        for (int i = 0; i < numRows; i++) {
//            //新定义一行
//            List<Integer> row = new ArrayList<>();
//            for (int j = 0; j <= i; j++) {
//                if (j == 0 || j == i) {
//                    row.add(1);
//                }else {
//                    //添加上一行的数据（上一行的j-1和j位置）
//                    row.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
//                }
//            }
//            //每一次将新的一行加入总的二维顺序表中
//            ret.add(row);
//        }
//        return ret;
//    }
//}


//class Solution {
//    public int removeElement(int[] nums, int val) {
//        int left = 0;
//        for (int right = 0; right < nums.length; right++) {
//            if (nums[right] != val) {
//                nums[left] = nums[right];
//                left++;
//            }
//        }
//        return left;
//    }
//}


//class Solution {
//    public int removeDuplicates(int[] nums) {
//        //快慢指针
//        int left = 0;
//        int right = 1;
//        while(right < nums.length){
//            if(nums[left] != nums[right]){
//                left++;
//                nums[left] = nums[right];
//            }
//            right++;
//        }
//        return left + 1;
//    }
//}


//class Solution {
//    public void merge(int[] nums1, int m, int[] nums2, int n) {
//        int pA = 0;
//        int pB = 0;
//        int cur = 0;
//        int[] sordNum = new int[m + n];
//        while (pA < m && pB < n) {
//            if (pA == m) {//nums1已满,放入nums2
//                cur = nums2[pB++];
//            } else if (pB == n) {//nums2已满，放入nums1
//                cur = nums1[pA++];
//            } else if (nums1[pA] < nums2[pB]) {//nums1的数据小于nums2
//                cur = nums1[pA++];
//            } else {//nums1的数据大于等于nums2
//                cur = nums2[pB++];
//            }
//            sordNum[pA + pB - 1] = cur;
//        }
//        for (int i = 0; i != m + n; ++i) {
//            nums1[i] = sordNum[i];
//        }
//    }
//}

//class Solution {
//    public ListNode reverseList(ListNode head) {
//        ListNode cur = head;
//        ListNode prev = null;
//        while (cur != null) {
//            ListNode tempNext = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = tempNext;
//        }
//        return prev;
//    }
//}


//class Solution {
//    public ListNode middleNode(ListNode head) {
//        ListNode fast = head;
//        ListNode slow = head;
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        return slow;
//
//    }
//}
//

//class Solution {
//    public static int count;
//    public void getLeafNodeCount(TreeNode root) {
//        if (root == null) {
//            return;
//        }
//        if (root.left == null && root.right == null) {
//            count++;
//        }
//        getLeafNodeCount(root.left);
//        getLeafNodeCount(root.right);
//    }
//
//    public int getLeafNodeCount2(TreeNode root) {
//        return 0;
//    }
//}


//class Solution {
//    public int getKLevelNodeCount(TreeNode root, int k) {
//        if (root == null) {
//            return 0;
//        }
//        if (k == 1) {
//            return 1;
//        }
//        return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);
//    }
//}

//class Solution {
//    public int getHeight(TreeNode root) {
//        if (root == null) {
//            return 0;
//        }
//        return getHeight(root.left) > getHeight(root.right) ? getHeight(root.left) : getHeight(root.right);
//    }
//}