二叉树_二叉搜索树查找最坏时间复杂度

一、为什么要树结构？

不像数组、链表是线性的数据结构，树是一种分层的非线性数据结构
（1）使用树的一个原因是：我们需要存储有分层关系的信息（比如说文件系统）
（2）另外一个是（BST）：当把树建成有一定的形式的树可以方便数据的查找（对于平衡的树，查找时间复杂度为O（logn））。
（3）同理对于这样一个树（AVL/红黑树）：他们的插入和删除的时间复杂度是（O（logn））
（4）相对于数组来说，树使用指针操作，可以动态的扩展节点。
二、二叉树的BFS和DFS
1、一个树典型的以两种方式进行遍历：
广度优先遍历（或者层序遍历）
深度优先遍历
中序遍历
前序遍历
后序遍历
2、四种遍历方式的比较
（1）时间复杂度上，上面四种遍历方式都需要O（n）的时间，因为他们都遍历了每一个node
（2）空间复杂度上，
对于BFS来说空间复杂度为O(w)其中w是二叉树的最大宽度，在层序遍历的时候，使用队列依次存储不同层次的nodes
对于DFS来说空间复杂度是O(h)其中h是二叉树的最大高度，在深度遍历的时候，使用stack来存储他们的祖先nodes
3、如何选择一种遍历方式？
平衡二叉树的高度为O(logn)，最坏的情况下出现倾斜树的时候成为O(n)
额外的空间是一个选择的标准
DFS一般使用的是递归的方法，递归方法的函数调用的开销也是一个因素
最重要的是：BFS总是从根节点开始，而DFS更倾向于从叶子节点开始，所以如果我们的问题是寻找查找离根节点很近的话我们要用BFS，反之使用DFS。

二叉树结构定义

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

求二叉树的最小深度

最小深度是从根节点到最近的叶子节点的最短路径的节点数

【思路】：遍历一棵二叉树，从根部看起，查看它是否有左右结点。有五种情况
1.没有根节点，那结果就是0
2.有根节点，没有左右子树，结果为1
3.没有左子树，有右子树。把右子树看成一棵新的树。
4.没有右子树，有左子树。把左子树看成一棵新的树。
5.既有左子树，又有右子树。那就把左右子树分别都看成新的树，最后比较谁的最近叶子的路径短，就取哪边。

//第一种方法层次遍历
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL)
            return 0;
        queue<TreeNode*>qtree;
        qtree.push(root);
        int num =1;
        while(!qtree.empty())
        {
            int cur=0;
            int last = qtree.size();
            while(cur < last)
            {
               TreeNode* temp = qtree.front();
                qtree.pop();
                if(temp->left==NULL&&temp->right==NULL)
                    return num;
                else
                {
                    if(temp->left)
                        qtree.push(temp->left);
                    if(temp->right)
                        qtree.push(temp->right);
                } 
                cur++;
            }
           num++;
        }
        return num;
    }
};
//第二种方法递归
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL)
            return 0;
        else if(root->left==NULL&&root->right==NULL)
            return 1;
        else if(root->left==NULL)
            return minDepth(root->right)+1;
        else if(root->right==NULL)
            return minDepth(root->left)+1;
        else
            return min(minDepth(root->right),minDepth(root->left))+1;
    }
};

求二叉树节点的个数

第一种方法，暴力求解，时间复杂度O（N）

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root)
            return 0;
        return countNodes(root->left)+countNodes(root->right)+1;
    }
};

第二种方法，利用完全二叉树的性质，第h层的节点个数为2^h-1

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root)
            return 0;
        int leftdepth=LeftTreedepth(root);
        int rightdepth=RightTreedepth(root);
        if(leftdepth==rightdepth)
            return (1<<leftdepth)-1;
        else
            return 1+countNodes(root->left)+countNodes(root->right);
    }
    int LeftTreedepth(TreeNode* root)
    {
        int depth=0;
        while(root)
        {
            depth++;
            root=root->left;
        }
        return depth;
    }
    int RightTreedepth(TreeNode* root)
    {
        int depth=0;
        while(root)
        {
            depth++;
            root=root->right;
        }
        return depth;
    }
};

 

二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
 
输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

第一种方法：递归法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        preorder(root, ret);
        return ret;
    }
    void preorder(TreeNode* root, vector<int> &ret)
    {
        if(root)
        {
            ret.push_back(root->val);
            preorder(root->left, ret);
            preorder(root->right, ret);
        }
    }
};

第二种方法：迭代法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode *>pre;
        while(root || !pre.empty())
        {
            if(root)
            {
                ret.push_back(root->val);
                pre.push(root);
                root = root->left;
            }
            else
            {
                root = pre.top();