数据结构补全计划

• 数据结构补全计划

1 二叉树

• 非递归式遍历

• https://www.jianshu.com/p/49c8cfd07410

• 前序遍历

  • /**
     * 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<pair<TreeNode*,bool>> mystack;
            mystack.push({root,false});//
            
            bool visited;
            while(!mystack.empty())
            {
                root=mystack.top().first;
                visited=mystack.top().second;
                mystack.pop();
                if(root==nullptr)
                    continue;
                if(visited)
                {
                    ret.push_back(root->val);
                }
                else
                {// 中 左 右
                    mystack.push({root->right,false});
                    mystack.push({root->left,false});
                    mystack.push({root,true});
                }
                    
            }
            return 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> inorderTraversal(TreeNode* root) {
             vector<int> path;
             stack< pair<TreeNode *, bool> > s;
            s.push(make_pair(root, false));
            bool visited;
            while(!s.empty())
            {
                root = s.top().first;
                visited = s.top().second;
                s.pop();
                if(root == NULL)
                    continue;
                if(visited)
                {
                    path.push_back(root->val);
                }
                else
                {
                    s.push(make_pair(root->right, false));// 变换三个的 true false 实现 前序 中序 后序 遍历
                    s.push(make_pair(root, true));
                    s.push(make_pair(root->left, false));
                }
            }
            return path;
         }

• 后序遍历

  • /**
     * 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> postorderTraversal(TreeNode* root) {
            vector<int> ret;
            stack<pair<TreeNode*,bool>> mystack;
            mystack.push({root,false});
            bool visited;
            while(!mystack.empty())
            {
                root=mystack.top().first;
                visited=mystack.top().second;
                mystack.pop();
                if(root==nullptr)
                    continue;
                if(visited)
                {
                    ret.push_back(root->val);
                }
                else//左 右 中
                {
                    mystack.push({root,true});
                    mystack.push({root->right,false});
                    mystack.push({root->left,false});
                }
            }
            return ret;
        }
    };

• 中序遍历添加null

  •     bool isSymmetric_error(TreeNode* root) {
           vector<int> ret;
           dfs(root,ret);
            
            int sz=ret.size();
            for(int i=0;i<sz/2;i++)
            {
                if(ret[i]!=ret[sz-1-i])
                    return false;
            }
            return true;
        }
        
        void dfs(TreeNode* root,vector<int>& ret)
        {
            //if(root==nullptr)
            //   return;
           if (root != nullptr && !(root->left==nullptr && root->right==nullptr))// 能够继续往下迭代 传递nullptr的只有 左右节点不同时为Nullptr的节点
    		    dfs(root->left, ret);
    
            if (root != nullptr)
                ret.push_back(root->val);
            else
                ret.push_back(INT_MAX);
    
            if (root != nullptr && !(root->left == nullptr && root->right == nullptr))
                dfs(root->right, ret);
        }
    /*
    比如输入 1 2 3 4 nullptr 5 nullptr
    输出 4 2 nullptr 1 5 3 nullptr
    */

• K层二叉树为满二叉树时最多，此时
  共有 2^k-1个节点
  第i层有2^(i-1)个节点
  叶子节点数为2^(K-1)
  如果为完全二叉树，此时一般会考叶子节点数
  一般设度为零的节点为n0、度为1的节点为n1、度为2的节点为n2，那么有
  n0+n1+n2 = 节点总数N
  n0 = n2+1
  n1 + 2*n2 = n-1