leetcode刷题笔记

226. 翻转二叉树 Easy

题目意思为将所有的结点的左子树和右子树都交换位置。那么意味着首先我们要进行便利操作

前序遍历

 public TreeNode invertTree(TreeNode root) {
         TreeNode treeNodeTemp=null;
     //前序遍历
         if (root==null) return root;
         //让传进来的root左子树和右子树交换位置
         treeNodeTemp = root.left;
         root.left = root.right;
         root.right = treeNodeTemp;
 //递归遍历
         invertTree(root.left);
         invertTree(root.right);
         return root;
    }

后序遍历

 public TreeNode invertTree(TreeNode root) {
 ​
     //后序遍历
     if (root==null) return root;
     invertTree(root.left);
     invertTree(root.right);
     //让传进来的root左子树和右子树交换位置
     TreeNode treeNodeTemp = root.left;
     root.left = root.right;
     root.right = treeNodeTemp;
     return root;
 }

中序遍历

值得注意的是，中序遍历和前序后续并不同，需要注意交换了位置

 public TreeNode invertTree(TreeNode root) {
 ​
         //中序遍历
         if (root==null) return root;
         invertTree(root.left);
         //让传进来的root左子树和右子树交换位置
         TreeNode treeNodeTemp = root.left;
         root.left = root.right;
         root.right = treeNodeTemp;
         
         //注意，在上面，已经将原本的左右子树交换了位置，所以这时候要遍历原先的右子树，应该访问左子树！
         invertTree(root.left);
 ​
         return root;
    }

层序遍历

在使用层序遍历之前，首先思考一下。二叉树的层序遍历我们是使用队列来实现的。即先进先出的特性

 public void levelOrderTraversal(Visitor visitor){
         if (root == null||visitor==null) return;
     Queue> queue = new linkedList>();
     //将根结点入队
     queue.offer(root);
     //只要队列不为空，就继续遍历
     while (!queue.isEmpty()){
     //取出队列的头结点
         Node node = queue.poll();
         //访问头结点 如果条件为true，直接返回
         if (visitor.visit(node.element)) return;
         //将根节点的左右结点入队
         if (node.left!=null) queue.offer(node.left);
         if (node.right!=null) queue.offer(node.right);
    }
    }

那么，我们根据现在翻转二叉树的需求，我们在弹出一个结点，对其进行访问的时候，应该交换其左右结点的顺序。

  public TreeNode invertTree(TreeNode root) {
         Queue queue = new linkedList();
         //先让根结点入队
          if (root==null) return root;
         queue.offer(root);
         //当队列中仍存在着结点时，一直循环下去，直到所有的结点都被访问
         while (!queue.isEmpty()) {
             //弹出将被访问的元素
             TreeNode node = queue.poll();
             //交换左右子结点的位置 这里并不需要考虑空值的异常，因为空值也可以进行交换
             TreeNode temp = node.left; 
             node.left = node.right;
             node.right = temp;
             //交换完后，看是否需要入队
             if (node.left!=null) queue.offer(node.left);
             if (node.right!=null) queue.offer(node.right);
        }
         return root;
    }

105. 从前序与中序遍历序列构造二叉树 mid

分析:根据二叉树前序遍历的规则得出，数组的第一元素个必然是根节点，那么我们可以拿着根节点去中序遍历中将数组分割开来，左边为左子树，右边为右子树。此时，我们可以得到一个规模更小的同样的问题。因此，此题解法使用递归。那么我们再来分析一下，我们应该在何时终止递归呢？ 答案是显而易见的，当我们传递的数组长度为0时，说明后续没有结点遍历了。在这里需要补充的是，在java中，拆分数组的api为Arrays.copyOfRange(T[ ] original,int from,int to)

{将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。

注意这里包括下标from，不包括上标to。}

 public TreeNode buildTree(int[] preorder, int[] inorder) {
         //左右子树长度都为0,重构完毕。
         if(preorder.length==0||inorder.length==0) return null;
         //拿到根节点
         TreeNode root = new TreeNode(preorder[0]);
         //找到根节点在中序遍历中的位置
         for(int i = 0;i 
 
12. 整数转罗马数字  mid
 
 
根据题意，是让我们将整数转化为罗马字符。所以我们为了储存返回结果，我们应该创建一个StringBuilder。我们动态模拟一遍便可知道此题的解法。输入一个num=1994,最终得到的结果是"MCMXCIV",即我们先找到一个小于num的最大的符号表中的数值，在此处为1000，减去它之后num变为994，将1000对应的字符"M"添加到StringBuilder中。依次类推，找到900，减去后num变为94,将900对应的字符"MC"添加到StringBuilder中......
 
故得到代码
 
 public String intToRoman(int num) {
         int[] values = {1,4,5,9,10,40,50,90,100,400,500,900,1000,};
         String[] symbols = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
         StringBuilder sb = new StringBuilder();
         //采用同一个下标的话，能保证symbol和value是一一对应的
         for(int i = values.length-1;i>=0;i--){
             while(num != 0 && num>=values[i])
            {
                 num -= values[i];
                 sb.append(symbols[i]);
            }
        }
         return sb.toString();
        }
 
空间复杂度O(1),时间复杂度O(1)