算法-树

发表于 | 分类于 | | 阅读次数

判断平衡二叉树

题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

在遍历树的每个结点的时候，调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1，按照定义它就是一棵平衡的二叉树。
这种思路对应的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool IsBalanced(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)
        return true;
    int left = TreeDepth(pRoot->m_pLeft);
    int right = TreeDepth(pRoot->m_pRight);
    int diff = left - right;
    if(diff > 1 || diff < -1)
        return false;
    return IsBalanced(pRoot->m_pLeft) && IsBalanced(pRoot->m_pRight);
}

上面的代码固然简洁，但我们也要注意到由于一个节点会被重复遍历多次，这种思路的时间效率不高。例如在函数IsBalance中输入上图中的二叉树，首先判断根结点（值为1的结点）的左右子树是不是平衡结点。此时我们将往函数TreeDepth输入左子树根结点（值为2的结点），需要遍历结点4、5、7。接下来判断以值为2的结点为根结点的子树是不是平衡树的时候，仍然会遍历结点4、5、7。毫无疑问，重复遍历同一个结点会影响性能。接下来我们寻找不需要重复遍历的算法。
如果我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。
下面是这种思路的参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)
{
    if(pRoot == NULL)
    {
        *pDepth = 0;
        return true;
    }
    int left, right;
    if(IsBalanced(pRoot->m_pLeft, &left)
        && IsBalanced(pRoot->m_pRight, &right))
    {
        int diff = left - right;
        if(diff <= 1 && diff >= -1)
        {
            *pDepth = 1 + (left > right ? left : right);
            return true;
        }
    }
    return false;
}

我们只需要给上面的函数传入二叉树的根结点以及一个表示结点深度的整形变量就可以了：

1
2
3
4
5
bool IsBalanced(BinaryTreeNode* pRoot)
{
    int depth = 0;
    return IsBalanced(pRoot, &depth);
}

在上面的代码中，我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后，我们可以根据它的左右子结点的深度判断它是不是平衡的，并得到当前结点的深度。当最后遍历到树的根结点的时候，也就判断了整棵二叉树是不是平衡二叉树了。

从上到下遍历二元树

输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印

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
     8
   /  \
  6    10
 / \   / \
5  7   9  11
输出 8   6   10   5   7   9   11。
void PrintFromTopToBottom(BTreeNode *pTreeRoot)
{
      if(!pTreeRoot)
          return;
      // get a empty queue
      deque<BTreeNode *> dequeTreeNode;
      // insert the root at the tail of queue
      dequeTreeNode.push_back(pTreeRoot);
      while(dequeTreeNode.size())
      {
            // get a node from the head of queue
            BTreeNode *pNode = dequeTreeNode.front();
            dequeTreeNode.pop_front();
            // print the node
            cout << pNode->m_nValue << ' ';
            // print its left child sub-tree if it has
            if(pNode->m_pLeft)
                  dequeTreeNode.push_back(pNode->m_pLeft);
            // print its right child sub-tree if it has
            if(pNode->m_pRight)
                  dequeTreeNode.push_back(pNode->m_pRight);
      }
}

二叉树后序遍历

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

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
         8
       /  \
      6    10
    / \    / \
   5   7   9  11
bool verifySquenceOfBST(int squence[], int length)
{
      if(squence == NULL || length <= 0)
            return false;
      // root of a BST is at the end of post order traversal squence
      int root = squence[length - 1];
      // the nodes in left sub-tree are less than the root
      int i = 0;
      for(; i < length - 1; ++ i)
      {
            if(squence[i] > root)
                  break;
      }
      // the nodes in the right sub-tree are greater than the root
      int j = i;
      for(; j < length - 1; ++ j)
      {
            if(squence[j] < root)
                  return false;
      }
      // verify whether the left sub-tree is a BST
      bool left = true;
      if(i > 0)
            left = verifySquenceOfBST(squence, i);
      // verify whether the right sub-tree is a BST
      bool right = true;
      if(i < length - 1)
            right = verifySquenceOfBST(squence + i, length - i - 1);
      return (left && right);
}

二元查找树的深度

题目：输入一棵二元树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

1
2
3
4
5
6
7
8
9
10
11
12
int TreeDepth(SBinaryTreeNode *pTreeNode)
{
      // the depth of a empty tree is 0
      if(!pTreeNode)
            return 0;
      // the depth of left sub-tree
      int nLeft = TreeDepth(pTreeNode->m_pLeft);
      // the depth of right sub-tree
      int nRight = TreeDepth(pTreeNode->m_pRight);
      // depth is the binary tree
      return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}

二元查找树的镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void MirrorRecursively(BSTreeNode *pNode)
{
      if(!pNode)
            return;
      // swap the right and left child sub-tree
      BSTreeNode *pTemp = pNode->m_pLeft;
      pNode->m_pLeft = pNode->m_pRight;
      pNode->m_pRight = pTemp;
      // mirror left child sub-tree if not null
      if(pNode->m_pLeft)
            MirrorRecursively(pNode->m_pLeft);  
      // mirror right child sub-tree if not null
      if(pNode->m_pRight)
            MirrorRecursively(pNode->m_pRight);
}

最大/小堆

100w个数中找出最大/i小的的100个数