leetcode刷题笔录-5

本文主要是介绍leetcode刷题笔录-5 - 一叶斋主人 - 博客园，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode刷题笔录-5 - 一叶斋主人 - 博客园

leetcode刷题笔录-5
数组转平衡二叉查找树
给定一个已排序的数组，将其转化为一棵平衡二叉查找树。平衡的概念是：任一节点的左子树和右子树的深度之差不大于1。
思路：数组是可以通过下标来访问的，所以去中点作为根节点，然后递归地生成左右子树。
实现：
/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode *sortedArrayToBST(vector<int> &num) {return _sortArrayToBST(num, 0, num.size()-1);}
private:TreeNode *_sortArrayToBST(vector<int> &num, int i, int j){if(i>j){return NULL;}else{int r = (i+j+1)/2;TreeNode *root = new TreeNode(num[r]);root->left = _sortArrayToBST(num, i, r-1);root->right = _sortArrayToBST(num, r+1, j);return root;}       }
}; 
链表转平衡二叉树
给定一个已排序的链表，将其转化为一棵平衡二叉查找树。
将链表转化为数组，再按照上一个方法实现，并为造成时间复杂度的增加。
实现：
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode *sortedListToBST(ListNode *head) {vector<int> num;while(head != NULL){num.push_back(head->val);head=head->next;}return _sortArrayToBST(num, 0, num.size()-1);}
private:TreeNode *_sortArrayToBST(vector<int> &num, int i, int j){if(i>j){return NULL;}else{int r = (i+j+1)/2;TreeNode *root = new TreeNode(num[r]);root->left = _sortArrayToBST(num, i, r-1);root->right = _sortArrayToBST(num, r+1, j);return root;}}
}; 
二叉树的层序遍历
给定一棵二叉树，按照节点深度的顺序输出所有节点的值，同一层的节点按照从左到右的顺序输出。比如，给出二叉树：
    3/ \9  20/  \15   7
则应当输出
[[3],[9,20],[15,7]
]
思路：在函数外维护一个值，记录当前节点的深度，输出时就依据这个值向二维数组中插入节点的值。
实现：
class Solution {
public:vector<vector<int>> levelOrder(TreeNode *root) {vector<vector<int>> rslt;_levelOrder(root, 0, rslt);return rslt;}void _levelOrder(TreeNode *root, int i, vector<vector<int>>& rslt){if(root == NULL){return;}else{if(i>(int)(rslt.size())-1){vector<int> tmp;tmp.push_back(root->val);rslt.push_back(tmp);}else{rslt[i].push_back(root->val);}_levelOrder(root->left, i+1, rslt);_levelOrder(root->right, i+1, rslt);            }}
}; 
二叉树的逆层序遍历
给定一棵二叉树，按照逆向层序遍历所有节点值。
思路：同上，获得结果后逆序即可。
class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode *root) {vector<vector<int>> rslt;_levelOrder(root, 0, rslt);vector<vector<int>> rsltReverse;for(int i=rslt.size()-1; i>=0; i--){rsltReverse.push_back(rslt[i]);}return rsltReverse;}void _levelOrder(TreeNode *root, int i, vector<vector<int>>& rslt){if(root == NULL){return;}else{if(i>(int)(rslt.size())-1){vector<int> tmp;tmp.push_back(root->val);rslt.push_back(tmp);}else{rslt[i].push_back(root->val);}_levelOrder(root->left, i+1, rslt);_levelOrder(root->right, i+1, rslt);            }}
}; 
同一棵树
给定两棵二叉树，判断其是否完全相同。
思路：如果两棵二叉树的节点值相同，而且左右子树都相同，那么二叉树就完全相同。注意考虑二叉树为空的情况。
/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSameTree(TreeNode *p, TreeNode *q) {if(p==NULL && q==NULL){return true;}else if(p==NULL || q==NULL){return false;}else if(p->val == q->val){return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}else{return false;}}
}; 
对称二叉树
给定一棵二叉树，判断其是否是对称的。
思路：这里应当把“一棵对称的二叉树”问题转化为“两棵对称的二叉树”问题。如果两棵二叉树节点值相同，而且树A的左子树与树B的右子树对称，树A的右子树与树B的左子树对称，那么这两棵二叉树就是对称的。如果某一棵二叉树的左右子树对称，那么它就是“一棵对称的二叉树”。
实现：
/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode *root) {if(root==NULL){return true;}else{return _isSymmetric(root->left, root->right);}}bool _isSymmetric(TreeNode *root1, TreeNode *root2){if(root1==NULL && root2==NULL){return true;}else if(root1==NULL || root2==NULL){return false;}else if(root1->val == root2->val){return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);}else{return false;}}
};
作者：一叶斋主人
出处： www.cnblogs.com/yiyezhai
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。