leetcode 刷题日志 2018-3-28

树：

404. 左叶子之和

求所有左叶子结点之和

. 递归法

分析：递归法遍历结点，找左叶子结点

        空指针判断

        有左子节点？是叶子结点？是的话更新value的值

int sumOfLeftLeaves(TreeNode* root) {

        if(!root) return ; // NULL

        int value = ;

        if(root->left){ //左子节点

                if(!root->left->left && !root->left->right) //是不是叶子结点？

                        value = root->left->val ;

        }

        return value + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);

}

.非递归法遍历寻找所有左叶子结点

int sumOfLeftLeaves(TreeNode* root) {

        if(!root) return ; //注意一定要处理空指针

        int res = ;

        queue<TreeNode*> q;

        q.push(root);

        while(!q.empty()){

                root = q.front();

                q.pop();

                if(root->left){ //左子节点

                        q.push(root->left);

                        if(!root->left->left && !root->left->right){ //是否为叶子结点

                                res += root->left->val;

                        }

                }

                if(root->right){

                        q.push(root->right);

                }

        }

        return res;

}

671. Second Minimum Node In a Binary Tree

题意：求二叉树第二小值，没有返回-

分析：用set存所有节点，最终容量大于2，代表存在第二小值，输出*(++set.begin())

```

int findSecondMinimumValue(TreeNode* root) {

            if(!root) return -;

            int res = -;

            queue<TreeNode* > q;

            q.push(root);

            set<int> s;

            while (!q.empty())

            {

                    root = q.front();

                    s.insert(root->val);

                    q.pop();

                    if (root->left) {

                            q.push(root->left);

                    }

                    if (root->right) {

                            q.push(root->right);

                    }

            }

            if(s.size() < ) res = -;

            else res = *(++s.begin());

            return res;

}

102. 二叉树的层次遍历

二叉树层次遍历且每层输出

算法记忆：一层一循环

```

vector<vector<int>> levelOrder(TreeNode* root) {

        vector<vector<int> > res;

        vector<int> tmp;

        if(!root) return res;

        queue<TreeNode*> q;

        q.push(root);

        int currentLevelTotalNum = ;

        while(!q.empty())

        {

            tmp.clear();

            currentLevelTotalNum = q.size();

            while(currentLevelTotalNum--){  //一层一循环

                root = q.front();

                tmp.push_back(root->val);

                q.pop();

                if(root->left){

                    q.push(root->left);

                }

                if(root->right){

                    q.push(root->right);

                }

            }

            res.push_back(tmp);

        }

        return res;

    }

```

107. 二叉树的层次遍历 II

分析：在正序层析遍历基础上，用栈临时存一下

vector<vector<int>> levelOrderBottom(TreeNode* root) {

        vector<vector<int> > res;

        vector<int> tmp;

        stack<vector<int> >tmps;

        if(!root) return res;

        queue<TreeNode*> q;

        q.push(root);

        int currentLevelTotalNum = ;

        while(!q.empty())

        {

            tmp.clear();

            currentLevelTotalNum = q.size();

            while(currentLevelTotalNum--){  //一层一循环

                root = q.front();

                tmp.push_back(root->val);

                q.pop();

                if(root->left){

                    q.push(root->left);

                }

                if(root->right){

                    q.push(root->right);

                }

            }

            tmps.push(tmp);

        }

        while(!tmps.empty()){

            res.push_back(tmps.top());

            tmps.pop();

        }

        return res;

    }

637. 二叉树的层平均值

题意：求二叉树每层平均值(double)所组成的数组

分析：每层求和取平均值

```

vector<double> averageOfLevels(TreeNode* root) {

        vector<double> res;

        if(!root) return res;

        queue<TreeNode* > q;

        q.push(root);

        int currentLevelTotalNum = , n = ;

        double tmpd;

        while(!q.empty()){

            currentLevelTotalNum = q.size();

            n = currentLevelTotalNum;

            tmpd = ;

            while(currentLevelTotalNum--){ //此层所有节点

                root = q.front();

                tmpd +=root->val;

                q.pop();

                if(root->left){

                    q.push(root->left);

                }

                if(root->right)

                {

                    q.push(root->right);

                }

            }

            tmpd /= n;

            res.push_back(tmpd);

        }

        return res;

    }

```

101. 对称二叉树

关键点在于递归比较。

题意：给定一个二叉树，检查它是否是它自己的镜像（即，围绕它的中心对称）。

分析：一个结点左子节点l，与右子节点r比较，递归的判断整棵树，l的左与r的右 且l的右跟r的左比较

抽取出递归模型如下

```

bool is(TreeNode* root1, TreeNode* root2){

        if(!root1 && !root2) return true;

        if(!root1) return false;

        if(!root2) return false;

        if(root1->val != root2->val){

            return false;

        }

        return is(root1->left,root2->right) && is(root1->right,root2->left);

    }

    bool isSymmetric(TreeNode* root) {

        if(!root) return true;

        return is(root->left,root->right);

    }

```

111. 二叉树的最小深度

题意：二叉树最小深度（从根节点到叶子结点的结点个数，包含两端）

分析：递归，

终结条件是 . root ==NULL   . 叶子结点

分别计算左子树、右子树的长度

取最小值，因为加上本结点所以最终返回值+

```

int minDepth(TreeNode* root) {

        if(!root) return ;

        if(!root->left && !root->right)

            return ;

        int left,right;

        if(root->left) left = minDepth(root->left);

        else left = INT_MAX;

        if(root->right) right = minDepth(root->right);

        else right = INT_MAX;

        return min(left,right) + ;

    }

```

104. 二叉树的最大深度

题意：最大二叉树深度

分析：递归法

.终结条件：

        . NULL

        . 叶子结点

. 分别计算左右子树长度

. 返回max(left,right)+ 加1是因为加上本结点

```

int maxDepth(TreeNode* root) {

        if(!root) return ;

        if(!root->left && !root->right) return ;

        int left, right;

        if(root->left) left = maxDepth(root->left);

        else left = INT_MIN;

        if(root->right) right = maxDepth(root->right);

        else right = INT_MIN;

        return max(left,right) + ;

    }

```

110. 平衡二叉树

题意：判断是否为平衡二叉树

分析：

本题是递归数深度遍历的一种应用。按照题目的意思，对于一个节点分别算出每个节点的左、右子树的深度，如果左、右子树深度差大于1，则可以该树非平衡。
那么递归每一个节点，一旦发现某一节点非平衡，就返回false，如果每一节点都平衡，则返回true：

```

//获取树的深度

int getDepth(TreeNode* root){

        if(!root) return ;

        return max(getDepth(root->left),getDepth(root->right)) + ;

    }

        //递归判断每个结点的子树是否满足长度只差不大于1

    bool isBalanced(TreeNode* root) {

        if(!root) return true;

        if(abs(getDepth(root->left) - getDepth(root->right)) > ){

            return false;

        }

        return isBalanced(root->left) && isBalanced(root->right);

    }

```

144. 二叉树的前序遍历 +1 2

题目：二叉树，前序遍历，迭代法

分析：DFS，用到栈，一直沿着左指针将沿路节点压入栈内，当到尽头，弹出top结点，将其右子树压入，右子树同样是先沿着左指针压到尽头后，向右展

记忆：深搜栈右展

```

vector<int> res;

    vector<int> preorderTraversal(TreeNode* root) {

        //递归

        if(root){

            res.push_back(root->val);

            preorderTraversal(root->left);

            preorderTraversal(root->right);

        }   return res;

}

vector<int> preorderTraversal(TreeNode* root) {

            //迭代

            vector<int> res;

            if(!root) return res;

            stack<TreeNode*> s;

            while (!s.empty() || root != NULL)

            {

                    if (root) { //至最左

                            res.push_back(root->val);

                            s.push(root);

                            root = root->left;

                    } else { //左到尽头，往右走

                            root = s.top();

                            s.pop();

                            root = root->right;

                    }

            }

            return res;

    }

```

94. 中序遍历二叉树 1+2

题意：二叉树中序遍历，迭代法

分析： DFS，利用栈，沿着左指针将一直到最左端的沿路所有节点依次压入栈中，每到到最左端向右展一下

记忆：深搜栈右展

```

vector<int> inorderTraversal(TreeNode* root) {

            stack< TreeNode* > s;

            TreeNode * p = root;

            vector<int> tmp;

            while(!s.empty() || p!=NULL){

                    while(p){ //到最左端

                            s.push(p);

                            p=p->left;

                    }

                    if(!s.empty()){  //右展一次

                            p=s.top();

                            tmp.push_back(p->val);

                            s.pop();

                            p=p->right;

                    }

            }

            return tmp;

    }

```

145. 二叉树的后序遍历 1 2 + 迭代法

分析：同样用到栈

记忆：+21入栈，处理两情况

//递归法

```

vector<int> res;

    vector<int> postorderTraversal(TreeNode* root) {

        if(root){

            postorderTraversal(root->left);

            postorderTraversal(root->right);

            res.push_back(root->val);

        }

        return res;

    }

```

//迭代法

```

vector<int> postorderTraversal(TreeNode* root) {

        vector<int> res;

        if(!root) return res;

        stack<TreeNode* > s;

        TreeNode *cur = root, *pre = NULL;

        s.push(cur);

        // 栈中的顺序是后序遍历的反序，先压入根，再压入右结点，左结点

        while (!s.empty())

        {

            cur = s.top();

            if((!cur->left && !cur->right) || (pre && (cur->left == pre || cur->right == pre))) //叶子结点直接处理 || 刚刚处理完左右结点

            {

                res.push_back(cur->val);

                pre = cur;

                s.pop();

            }

            else{

                if(cur->right){

                    s.push(cur->right);

                }

                if (cur->left)

                    s.push(cur->left);

            }

        }

        return res;

    }

```

617. 合并二叉树

/*

题意：合并两棵二叉树，对应结点相加，否则补上

分析：递归实现

                根节点都为空，return NULL

                根节点都不为空，求和

                根节点有一个空，补上

                进一步分析左右子树

前三步就是抽取出来的子过程

*/

```

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

        if(!t1 && !t2) return NULL;

        if (t1 && t2) {

            t1->val += t2->val;

            t2->val = t1->val;

        }

        else if (t1) {

            t2 = new TreeNode(t1->val);

        }

        else if (t2) {

            t1 = new TreeNode(t2->val);

        }

        t1->left = mergeTrees(t1->left,t2->left);

        t1->right = mergeTrees(t1->right,t2->right);

        return t1;

    }

```

114. 二叉树转换链表

题意：二叉树转换链表；将所有结点编程右指针连接

分析：将前序遍历序列，顺序串联

```

//迭代版，前序遍历

    vector<TreeNode*> preOrder2(TreeNode* root) {

        vector<TreeNode*> res;

        if(!root) return res;

        stack<TreeNode*> s;

        TreeNode* p = root;

        while(!s.empty() || p)

        {

            while(p){   //一直往左

                res.push_back(p);

                s.push(p);

                p = p->left;

            }

            if(!s.empty()){ //右展

                p = s.top();

                s.pop();

                p = p->right;

            }

        }

        return res;

    }

    // 注意只需保留头指针，指针传递，传递方保留着头指针，他顺着访问就是了

    void flatten(TreeNode* root) {

        if(!root) return ;

        //前序遍历结果

        vector<TreeNode*> preOrderV = preOrder2(root);

        int len = preOrderV.size();

        root->left = NULL;

        root->right = NULL;

        //链表形成

        for(int i=;i<len;i++)

        {

            root->right = preOrderV[i];

            root = preOrderV[i];

            root->left = NULL;

            root->right =NULL;

        }

    }

```

112. 路径总和

/*

题意：路径总和，给一棵二叉树和一个整数sum，问是否存在从根节点到叶节点的路径，求和等于sum

分析：递归，和递减

*/

```

bool hasPathSum(TreeNode* root, int sum) {

        if(!root) return false;

        if(root->val == sum){ //恰好有叶节点满足

            if(!root->left && !root->right){

                return true;

            }

        }

        return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);

    }

```

113. 路径总和 II

题意：找出一棵二叉树里，路径（根结点到叶结点）上结点之和等于sum的所有路径

分析：经典递归回溯问题，搜集路径上所有节点时，注意遇到结点push,用完节点pop

经典递归回溯

```

vector<vector<int> >result;

    vector<int> path;

    // 经典递归回溯问题

    void findPath(TreeNode* root, int sum) {

        if(!root) return ;

        if(root->val == sum && !root->left && !root->right ) { //find a path equal sum && It's a leaf node

            path.push_back(root->val);

            result.push_back(path); // find a path

            path.pop_back(); //!!

            return ;

        }

        path.push_back(root->val); // 经过节点压入

        findPath(root->left, sum - root->val);

        findPath(root->right, sum - root->val);

        path.pop_back(); // 对与此节点的左右子树都已经处理完，弹出此节点 !

    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {

        vector<vector<int>> res;

        if(!root) return res;

        findPath(root, sum);

        return result;

    }

```

257. 二叉树的所有路径

/*

题意：输出二叉树所有路径

分析：经典递归回溯法

*/

```

vector<vector<int> >allPath; //所有路径

    vector<int> aPath; //单条路径

    // 经典递归回溯法求二叉树所有路径

    void findPath(TreeNode* root) {

        if(!root) return ;

        if(!root->left && !root->right) { //leaf node

            aPath.push_back(root->val);

            allPath.push_back(aPath);   // a path

            aPath.pop_back();

            return ;

        }

        aPath.push_back(root->val);

        findPath(root->left);

        findPath(root->right);

        aPath.pop_back();

    }

    vector<string> binaryTreePaths(TreeNode* root) {

        vector<string> res;

        if(!root) return res;

        findPath(root);

        int len = allPath.size();

        string tmpS = "";

        for (int i=; i<len; i++) {

            tmpS = std::to_string(allPath[i][]);

            for (int j=; j<allPath[i].size(); j++) {   //形成路径字符串

                tmpS += ("->" + std::to_string(allPath[i][j]));

            }

            res.push_back(tmpS);

        }

        return res;

    }

```

巴特西

leetcode 刷题日志 2018-3-28

最新文章

热门文章