java训练day 17 ①杨辉三角(二维数组)②二叉树的镜像(数据结构+递归)

目录

①杨辉三角

②二叉树的镜像

①杨辉三角

import java.util.*;
public class Main {
    public static void main(String[]args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            //定义一个二维数组来存放杨辉三角
            //将题目中的杨辉三角靠左排列更容易理解
            //1
            //111
            //12321
            //1367631
            int m = 2 * n - 1; //杨辉三角每一行的个数为2n-1
            int[][] arr = new int[n][m];
            //初始化二维数组
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = 0; //将二维数组初始化为0
                }
            }
            //1行1列的值先进行初始化为1
            arr[0][0] = 1;
            //开始构建数组值
            for (int i = 1; i < n; i++) {
                //第一行已经构造完毕，在数组中是arr【0】
                //因而循环直接从1开始，构建到下标为n-1的数组则
                //构建完成
                //由于每一行第一个和最后一个的均为1
                arr[i][0] = arr[i][2 * i] = 1;
                for (int j = 1; j < 2 * i; j++) {
               //当j==1，则j-2下标越界，arr[i-1][j-2]视为0；
               //当j！=1时，则对应的值为上一行三数之和相加
                    if (j == 1) {
                        arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
                    } else {
                        arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1] + arr[i - 1][j - 2];
                    }
                }
            }//遍历偶数
            int k = 0;
            for (; k < m; k++) {
                if (arr[n - 1][k] % 2 == 0) {
                    System.out.println(k + 1);
                    break;
                }
            }
            if (k == m) {
                System.out.println(-1);
            }
        }
    }
}

②二叉树的镜像

import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        //当树为空树时，直接返回null即可。空树的镜像还是null
        if(pRoot==null){
            return null;
        }
        //当跟的左树和右树均为空树时，则说明只有一个根节点，则不用取镜像了
        //直接返回根节点即可
        //这也作为了下面递归的中止条件，当递归左右树时满足if条件则将当前根节点返回
        if(pRoot.left==null&&pRoot.right==null){
            return pRoot;
        }
        //把根节点的左树变为右树，右树变为左数
        TreeNode temp=pRoot.left;
        pRoot.left=pRoot.right;
        pRoot.right=temp;
        //这时pRoot.left以及下面的左右树子节点已到右边
        //递归遍历左树和右树调换位置
        if(pRoot.left!=null){
            Mirror(pRoot.left);
        }if(pRoot.right!=null){
            Mirror(pRoot.right);
        }
        //全部执行结束后则会返回最初那层，返回根节点
        return pRoot;
    }
}