面试题随笔-21/4/5

发表于 | 分类于 | 次

二叉搜索树查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 二叉搜索树的查找
public TreeNode searchBST(TreeNode root, int val) {
  if (root == null)
    return null;

  if (root.value > val) {
    return searchBST(root.left, val);
  } else if (root.value < val) {
    return searchBST(root.right, val);
  } else {
    return root;
  }
}

// 迭代法
public TreeNode searchBST2(TreeNode root, int val) {
  while (root != null) {
    if (root.value == val) {
      return root;
    } else if (root.value > val) {
      root = root.left;
    } else {
      root = root.right;
    }
  }

  return null;
}

二叉搜索树删除某个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public TreeNode deleteNode(TreeNode root, int key) {
  if (root == null) {
    return null;
  }

  if (key < root.value) {
    root.left = deleteNode(root.left, key);
    return root;
  }

  if (key > root.value) {
    root.right = deleteNode(root.right, key);
    return root;
  }

  // 到这里意味已经查找到目标
  if (root.right == null) {
    // 右子树为空
    return root.left;
  }
  if (root.left == null) {
    // 左子树为空
    return root.right;
  }

  TreeNode minNode = root.right;
  while (minNode.left != null) {
    // 查找后继
    minNode = minNode.left;
  }

  root.value = minNode.value;
  root.right = deleteMinNode(root.right);
  return root;
}

private TreeNode deleteMinNode(TreeNode root) {

  TreeNode pRight = null;

  if (root.left == null) {
    pRight = root.right;
    root.right = null;
    return pRight;
  }
  root.left = deleteMinNode(root.left);
  return root;
}

平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//平衡二叉树
public boolean isBalanced(TreeNode root) {
  if (root == null) {
    return true;
  }

  if (!isBalanced(root.left) || !isBalanced(root.right)) {
    return false;
  }

  int leftH = maxDepth(root.left) + 1;
  int rightH = maxDepth(root.right) + 1;

  if (Math.abs(leftH - rightH) > 1) {
    return false;
  }
  return true;
}

private int maxDepth(TreeNode root) {
  if (root == null) {
    return 0;
  }

  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

完全二叉树，求节点个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 完全二叉树, 求该树的节点个数。
public int countNodes(TreeNode root) {
  if (root != null) {
    return 1 + countNodes(root.right) + countNodes(root.left);
  }

  return 1 + countNodes(root.right) + countNodes(root.left);
}

public int countNodes2(TreeNode root) {
  if (root == null) {
    return 0;
  }

  int left = countLevel(root.left);
  int right = countLevel(root.right);
  if (left == right) {
    return countNodes2(root.right) + (1 << left);
  } else {
    return countNodes2(root.left) + (1 << right);
  }
}

private int countLevel(TreeNode root) {
  int level = 0;
  while (root != null) {
    level++;
    root = root.left;
  }
  return level;
}