算法极客班

12.BFS与二叉搜索树

2015-08-12  本文已影响322人  偷天神猫

Binary Tree BFS Traversal

二叉树层次遍历


//刚开始没看懂，自己画图细看几遍发生特别精妙，赞一个
//一定要记住队列是先进先出的

void levelTraversal(TreeNode *root)
{
    queue<TreeNode *> nodeQueue;
    TreeNode *currentNode;
    if (!root) {
        return;
    }

    //先塞入根节点
    nodeQueue.push(root);

    while (!nodeQueue.empty()) {

        //当前节点值为queue中的第一个数据。
        currentNode = nodeQueue.front();

        //做进一步的处理，比如需要打印
        processNode(currentNode);
        if (currentNode->left) {
            nodeQueue.push(currentNode->left);
        }
        if (currentNode->right) {
            nodeQueue.push(currentNode->right);
        }

        //弹出当前的数据
        nodeQueue.pop();
    }
}

Binary Tree to Linked Lists

Covert a binary tree to linked lists. Each linked list is correspondent to all the nodes at the same level.

核心问题：如何判断这一层已经遍历完毕？

解题思路：利用优先队列

代码示例：


//为什么你老是喜欢把你定义的result写成answer，我真的要报警了

ool isDummyNode(TreeNode *node) {
    return (node->left == node);
}

vector<list<TreeNode *>> linkedListsFromTree(TreeNode *root) {
    vector<list<TreeNode *>> result;
    list<TreeNode *> levelList;
    queue<TreeNode *> nodeQueue;
    TreeNode *currentNode;

    TreeNode dummyNode;
    dummyNode.left = &dummyNode;


    if (!root) {
        return result;
    }

    nodeQueue.push(&dummyNode);//dummyNode用于分割层
    nodeQueue.push(root);

    while (!nodeQueue.empty()) {
        currentNode = nodeQueue.front();
        if (isDummyNode(currentNode)) {
            if (!levelList.empty()) {

                //若首节点时dummyNode且level不为空，就将该level塞入我们的最终结果列表
                //然后清空level。代表了一层遍历的结束，开始遍历二叉树的下一层
                result.push_back(levelList);
                levelList.clear();
            }
            nodeQueue.pop();
            if (nodeQueue.empty()) {
                break;
            } else {
                //每次遍历完一层，nodeQueue都会被塞入一个dummyNode
                nodeQueue.push(&dummyNode);
            }

        } else {
            levelList.push_back(currentNode);
            if (currentNode->left) {
                nodeQueue.push(currentNode->left);
            }
            if (currentNode->right) {
                nodeQueue.push(currentNode->right);
            }
            nodeQueue.pop();
        }
    }

    return result;
}

Binary Tree Level Order Traversal

示例代码：


// use 2 variables 
//利用两个变量来判断一层是否遍历完，标志位为nodesInCurrentLevel，
//当其为0时一层遍历结束，输入endl换行
void printLevelOrder(BinaryTree *root) {
  if (!root) return;
  queue<BinaryTree*> nodesQueue;
  int nodesInCurrentLevel = 1;
  int nodesInNextLevel = 0;

  nodesQueue.push(root);
  while (!nodesQueue.empty()) {
    BinaryTree *currNode = nodesQueue.front();
    nodesQueue.pop();
    nodesInCurrentLevel--;
    if (currNode) {
      cout << currNode->data << " ";
      nodesQueue.push(currNode->left);
      nodesQueue.push(currNode->right);
      nodesInNextLevel += 2;
    }
    if (nodesInCurrentLevel == 0) {
      cout << endl;
      nodesInCurrentLevel = nodesInNextLevel;
      nodesInNextLevel = 0;
    }
  }
}

// use 2 queue
//使用队列来判断，当currentLevel时一层遍历结束
void printLevelOrder(BinaryTree *root) {
  if (!root) return;
  queue<BinaryTree*> currentLevel, nextLevel;
  currentLevel.push(root);
  while (!currentLevel.empty()) {
    BinaryTree *currNode = currentLevel.front();
    currentLevel.pop();
    if (currNode) {
      cout << currNode->data << " ";
      nextLevel.push(currNode->left);
      nextLevel.push(currNode->right);
    }
    if (currentLevel.empty()) {
      cout << endl;
      swap(currentLevel, nextLevel);
    }
  }
}

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes'values. (ie, from left to right, level by level from leaf to root).
For example: Given binary tree {3,9,20,#,#,15,7},

反式反式

return its bottom-up level order traversal as:

反式1反式1

Binary Tree Zigzag Level Order Traversal

原题地址

示例代码：


void printLevelOrderZigZag(BinaryTree *root) {
  stack<BinaryTree*> currentLevel, nextLevel;
  bool leftToRight = true;
  currentLevel.push(root);
  while (!currentLevel.empty()) {
    BinaryTree *currNode = currentLevel.top();
    currentLevel.pop();
    if (currNode) {
      cout << currNode->data << " ";
      if (leftToRight) {
        nextLevel.push(currNode->left);
        nextLevel.push(currNode->right);
      } else {
        nextLevel.push(currNode->right);
        nextLevel.push(currNode->left);
      }
    }
    if (currentLevel.empty()) {
      cout << endl;
      leftToRight = !leftToRight;
      swap(currentLevel, nextLevel);
    }
  }
}

Binary Search Tree

二分查找树(Binary Search Tree, BST)是二叉树的一种特例，对于二分查找树的任意节点，该节点储存的数值一定比左子树的所有节点的值大比右子树的所有节点的值小(该节点储存的数值一定比左子树的所有节点的值小比右子树的所有节点的值大)。基于这个特性，二分查找树通常被用于维护有序数据。二分查找树查找、删除、插入的效率都会高于一般的线性数据结构。

bstbst

平衡二叉树的概念。所谓平衡二叉树，是指一棵树的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

有序数组变为二分查找树

代码示例：


TreeNode* helper(vector<int>num, int first, int last){
    if(first > last){
        return NULL;
    }
    if (first == last) {
        TreeNode* parent = new TreeNode(num[first]);
        return parent;
    }
    int mid = (first + last) / 2;
    TreeNode *leftchild = helper(num, first, mid - 1);
    TreeNode *rightchild = helper(num, mid + 1, last);
    TreeNode *parent = new TreeNode(num[mid]);
    parent->left = leftchild;
    parent->right = rightchild;
    return parent;
}

TreeNode *sortedArrayToBST(vector<int> &num) {
    if(num.size() == 0)
        return NULL;
    if(num.size() == 1){
        TreeNode* parent = new TreeNode(num[0]);
        return parent;
    }
    int first = 0;
    int last = (int)num.size() - 1;
    return helper(num, first, last);
}

Is Binary Search Tree

错误例子：


/************
    10  
    / \  
    5 15  
      / \  
     6  20  
*************/

bool isValidBST(TreeNode* root) {
    if(root==NULL)
        return true;
    else if(root->left&&!root->right)
        return isValidBST(root->left)&&(root->val>root->left->val);
    else if(!root->left&&root->right)
        return isValidBST(root->right)&&(root->val<root->right->val);
    else if(root->left&&root->right)
        return isValidBST(root->left)&&isValidBST(root->right)&&(root->val>root->left->val)&&(root->val<root->right->val);
    else
        return true;
}

正确示例


bool helper(TreeNode *root, int min, int max){
    if(!root) return true;
    if((root->val < max || (root->val == INT_MAX && root->right == NULL)) &&
        (root->val > min || (root->val == INT_MIN && root->left == NULL)) &&
        helper(root->left, min, root->val) &&
        helper(root->right, root->val, max))
          return true;
    return false;
}

bool isValidBST(TreeNode *root) {
    return helper(root, INT_MIN, INT_MAX);
}

Trie

字典树(trie or prefix tree)是一个26(26个英文字母)叉树，用于在一个集合中检索一个字符串，或者字符串前缀。字典树的每个节点有一个指针数组代表其所有子树，其本质上是一个hash table，因为子树所在的位置(index)本身，就代表了节点对应的字母。节点与每个兄弟具有相同的前缀，也被称为prefix tree。

Trie Structure


class TrieNode{
private:
    T mContent;
    vector<TrieNode*> mChildren;

public:
    Node();
    ~Node();
    friend class Trie;
};

class Trie{
public:
    Trie();
    ~Trie();
    void addWord(string s);
    bool searchWord(string s);
    void deleteWord(string s);

private:
    TrieNode* root;
};

Mock Interview

Lowest Common Ancestor(LCA)

最近的公共衔接点

Given a binary tree and two nodes. Find the lowest common ancestor of the two nodes in the tree.
For example, the LCA of D & E is B.

lcalca

示例代码：


TreeNode *commonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (covers(root->left, p) && covers(root->left, q)) {
        return commonAncestor(root->left, q, p);
    }
    if (covers(root->right, p) && covers(root->right, q)) {
        return commonAncestor(root->right, q, p);
    }
    return root;
}

bool covers(TreeNode *root, TreeNode *p) {
    if (root == NULL) {
        return false;
    }
    if (root == p) {
        return true;
    }
    return covers(root->left, p) || covers(root->right, p);
}

// bottom to top

TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
        // return either A or B or NULL
        if (NULL == root || root == A || root == B) return root;

        TreeNode *left = lowestCommonAncestor(root->left, A, B);
        TreeNode *right = lowestCommonAncestor(root->right, A, B);

        // A and B are on both sides
        if ((NULL != left) && (NULL != right)) return root;

        // either left or right or NULL
        return (NULL != left) ? left : right;
    }

Homework:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:


/************
     1  
   /   \  
  2     2  
 / \   / \  
3   4 4   3  

************/

But the following is not:

/**********
  1  
 / \  
 2  2  
  \  \  
   3  3  

**********/
上一篇 下一篇

猜你喜欢

热点阅读