剑指Offer之Java算法习题精讲N叉树的遍历及数组与字符串

题目一

解法

/*
// Definition for a Node.
class Node {
  public int val;
  public List<Node> children;
  public Node() {}
  public Node(int _val) {
      val = _val;
  }
  public Node(int _val, List<Node> _children) {
      val = _val;
      children = _children;
  }
};
*/

class Solution {
  ArrayList<Integer> list = new ArrayList<Integer>();
  public List<Integer> preorder(Node root) {
      if (root == null) return list;
      list.add(root.val);
      for(int i=0;i<root.children.size();i++){
          preorder(root.children.get(i));
      }
      return list;
  }
}

题目二

 解法

/*
// Definition for a Node.
class Node {
  public int val;
  public List<Node> children;
  public Node() {}
  public Node(int _val) {
      val = _val;
  }
  public Node(int _val, List<Node> _children) {
      val = _val;
      children = _children;
  }
};
*/

class Solution {
  ArrayList<Integer> list = new ArrayList<Integer>();
  public List<Integer> postorder(Node root) {
      if(root==null) return list;
      for(int i = 0;i<root.children.size();i++){
          postorder(root.children.get(i));
      }
      list.add(root.val);
      return list;
  }
}

题目三

解法

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
  public String tree2str(TreeNode root) {
      // root为空返回""
      if(root==null){
          return "";
      }
      // root左右为空
      if(root.left==null&&root.right==null){
          return root.val+"";
      }
      // root右为空
      if(root.right==null){
          return root.val+"("+tree2str(root.left)+")";
      }
      // root左右不空或是左不为空
      return root.val+"("+tree2str(root.left)+")"+"("+tree2str(root.right)+")";
  }
}

题目四

解法

class Solution {
  public int maximumProduct(int[] nums) {
      Arrays.sort(nums);
      int n = nums.length;
      // 拿到最大三个数，或者最小两个数和最大一个数
      int ans = Math.max(nums[n-1]*nums[n-2]*nums[n-3],nums[n-1]*nums[0]*nums[1]);
      return ans;
  }
}

// 拿到最大三个数，或者最小两个数和最大一个数
class Solution {
  public int maximumProduct(int[] nums) {
      // 最小的和第二小的
      int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
      // 最大的、第二大的和第三大的
      int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
      for(int n:nums){
          if(n<min1){
              min2 = min1;
              min1 = n;
          }else if(n<min2){
              min2 = n;
          }
          if(n>max1){
              max3 = max2;
              max2 = max1;
              max1 = n;
          }else if(n>max2){
              max3 = max2;
              max2 = n;
          }else if(n>max3){
              max3 = n;
          }
      }
      return Math.max(min1*min2*max1,max1*max2*max3);
  }
}

到此这篇关于剑指Offer之Java算法习题精讲N叉树的遍历及数组与字符串的文章就介绍到这了,更多相关Java N叉树的遍历内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/wai_58934/article/details/123260993