剑指offer-困难篇

Posted on | In ,

对称的二叉树

题目描述：叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：递归，编写方法，判断以两根节点的二叉树是否对称

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
  boolean isSymmetrical(TreeNode pRoot){
    if(pRoot == null) return true;
    return isSymmetrical(pRoot.left, pRoot.right);
  }

  boolean isSymmetrical(TreeNode node1, TreeNode node2){
    if(node1 == null && node2 == null) return true;
    if(node1 == null || node2 == null) return false;
    if(node1.val != node2.val) return false;
    return isSymmetrical(node1.left, node2.right) && isSymmetrical(node1.right, node2.left);
  }
}


数组中的逆序对

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

思路：

  1. 穷举：超时；
1
2
3
4
5
6
7
8
9
10
11
public int InversePairs(int [] array) {
  int count = 0;
  for(int i = 1;i < array.length;i++){
    for(int j = 0;j < i;j++){
      if(array[j] > array[i]){
        count++;
      }
    }
  }
  return count%1000000007;
}
1
2




从上往下打印二叉树

题目描述：从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：二叉树层次遍历，利用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
  if(root == null) return new ArrayList<Integer>();
  ArrayList<Integer> res = new ArrayList<Integer>();
  Queue<TreeNode> queue = new LinkedList<>();
  
  queue.add(root);
  while(!queue.isEmpty()){
    int n = queue.size();
    for(int i = 0; i < n; i++){
      TreeNode node = queue.poll();
      res.add(node.val);
      if(node.left != null) queue.add(node.left);
      if(node.right != null) queue.add(node.right);
    }
  }
  return res;
}