赞
踩
树是n(n>=0)个节点的有限集,且这些节点满足如下关系:
1.有且仅有一个节点没有父节点,该节点称为树的根。
2.除根外,其余的每个节点都有且仅有一个父节点
3.树中的每一个节点都构成一个以它为根的树。
二叉树有前序遍历、中序遍历和后序遍历。
二叉树有深度优先遍历(DFS使用栈)和广度优先遍历(BFS使用队列):
//深度优先搜索 //利用栈,现将右子树压栈再将左子树压栈 void DepthFirstSearch(BitNode *root) { stack<BitNode*> nodeStack; nodeStack.push(root); while (!nodeStack.empty()) { BitNode *node = nodeStack.top(); cout << node->data << ' '; nodeStack.pop(); if (node->right) { nodeStack.push(node->right); } if (node->left) { nodeStack.push(node->left); } } } //广度优先搜索 void BreadthFirstSearch(BitNode *root) { queue<BitNode*> nodeQueue; nodeQueue.push(root); while (!nodeQueue.empty()) { BitNode *node = nodeQueue.front(); cout << node->data << ' '; nodeQueue.pop(); if (node->left) { nodeQueue.push(node->left); } if (node->right) { nodeQueue.push(node->right); } } }
**第一题:**给定一个二叉树与整数sum,找出所有从根节点到叶结点的路径,这些路径上的节点值累加和为sum。leetcode 113
算法思路:从根节点深度遍历二叉树,先序遍历时,将该节点值存储至path栈中(vector实现),使用path_value累加节点值。
当遍历至叶结点时,检查path_value值是否为sum,若为sum,则将path push进入result结果中。
然后将节点值从path栈中弹出,path_value减去节点值。
class Solution { public: void preorder(TreeNode* node,int sum, vector<int>& path,int path_value,vector<vector<int>>& result){ if(!node) return; path_value+=node->val; //累加和 path.push_back(node->val); if(path_value==sum && node->right==NULL && node->left==NULL){ //到叶结点 result.push_back(path); //路径push到result中 } preorder(node->left,sum, path,path_value, result); preorder(node->right,sum, path,path_value, result); path_value-=node->val; path.pop_back(); } vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> result; vector<int> path; int path_value=0; preorder(root,sum,path,path_value,result); return result; } };
第二题:求最近的公共祖先:leetcode 236
已知二叉树,求二叉树中给定的两个节点的最近公共祖先。
两节点v与w的最近公共祖先u,满足在树上最低(离根最远),且v,w两个节点都是u的子孙。
例如下图中,3是5和6的公共祖先,5是6和4的公共祖先
算法思路:
1.两个节点的公共祖先一定在从根节点,至这两个节点的路径上。
2.由于求公共祖先中的最近公共祖先,那么即同时出现在这两条路经上的离根节点最远的节点(或离两个最近)
3.最终算法:求p节点路径,q节点路径,两路径上最后一个相同的节点。
首先我们求根节点至某节点的路径(深度搜索)
1.从根节点遍历(搜索)至该节点,找到该节点后就结束搜索。
2.将遍历过程中遇到的节点按照顺讯存储起来,这些节点即路径节点。
void preorder(TreeNode* node, TreeNode* search, vector<TreeNode*>path, vector<TreeNode*>result,int finish){
if(!node||finish==1) return;
path.push_back(node);
if(node==search){
result=path;
finish=1;
}
preorder( node->left, search, path, result,finish);
preorder( node->right, search, path, result,finish);
path.pop_back();
}
finish表示是否找到的标志位,如果找到为1,找不到为0; 开始我们先把node节点放到path里面,然后递归树的左孩子和右孩子,结束遍历node时,将node节点弹出path栈。
第二步:我们求两路径上最后一个相同的节点:
1.求出较短路径的长度n;
2.同时遍历p节点的路径与q节点的路径,遍历n个节点,最后一个发现的相同节点,即最近公共祖先。
这个很简单啦:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { vector<TreeNode* > path; //临时节点 vector<TreeNode* >path_p; //p的路径 vector<TreeNode* >path_q; //q的路径 int finish=0; preorder(root,p, path, path_p,finish); //获取p的路径 path.clear(); finish=0; preorder(root,q, path, path_q,finish); //获取q的路径 int len=0; if(path_p.size()<path_q.size()) len = path_p.size(); else len = path_q.size(); TreeNode* result; for(int i=0;i<len;i++) { if(path_p[i]==path_q[i]) //找到了最近的公共祖先 result = path_p[i]; } return result; }
第三题:二叉树转链表:
给定一个二叉树,将该二叉树就地(in-place)转换为单链表。单链表中节点顺序为二叉树前序遍历顺讯。leetcode 114
思考:如果不是就地转换的话。我们可以使用一个vector。前序遍历二叉树,将节点指针push进入vector,顺序遍历vector中的节点,连接相邻两节点,形成链单链表。
void flatten(TreeNode*root){
vector<TreeNode*> node_vec;
preorder(root,node_vec);
for(int i=1;i<node_vec.size();i++){
node_vec[i-1]->left = NULL;
node_vec[i-1]->right= node_vec[i]->left;
}
}
void preorder(TreeNode* root,vector<TreeNode*>& node_vec){
if(!root) return;
node_vec.push_back(node);
preorder(root->left,node_vec);
preorder(root->right,node_vec);
}
算法思路:将一个二叉树的左树和右树分开如图;依次将左右子树拉直,也就是节点的左孩子指向null,右孩子指向下一个。
左树的开头节点记为left,结束记为left_last。右树的开头节点记为right,结束记为right_last。然后将left_last->right = right
right_last = last;
void flatten(TreeNode* root) { TreeNode* last = NULL; preorder(root,last); } void preorder(TreeNode* root, TreeNode*& last){ if(!root) return; if(!root->left && !root->right){ last = root; return; } TreeNode* left = root->left; TreeNode* right = root->right; TreeNode* last_left = NULL; TreeNode* last_right = NULL; if(left){ preorder( root->left, last_left); root->left = NULL; //根的左子树置为空 root->right = left; //根的右子树指向左子树第一个 last = last_left; } if(right){ preorder( root->right, last_right); if(last_left){ //如果左子树存在 last_left->right = right; } last = last_right ; } }
二叉树的宽度优先搜索。层次遍历使用队列对遍历节点进行存储,先进入队列的结点,优先遍历拓展其左孩子和右孩子。
第四题:给定一个二叉树,假设从该二叉树的右侧观察它,将观察到得到节点按照从上到下的顺序输出。leetcode 199
思考:题目的意思就是说求层次遍历二叉树,每个层中的最后一个节点。
层次遍历时,将节点与层数绑定为pair,压入队列时,将节点与层数同时压入队列,并记录每一层中出现的最后一个节点。
在层次遍历中,每一层中的最后一个节点最后遍历到,随时更新对每层的最以后一个节点即可。
class Solution { public: vector<int> rightSideView(TreeNode* root) { queue<TreeNode*> q; q.push(root); vector<int> res; if (!root) return res; while (!q.empty()) { int n = q.size(); for (int i = 0; i < n; ++i) { TreeNode* t = q.front(); if (i == 0) res.push_back(t->val); q.pop(); if (t->right)q.push(t->right); if (t->left)q.push(t->left); } } return res; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。