二叉树------路径

求一棵二叉树从根到所有叶子的路径集合

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; void path(TreeNode *root,vector<vector<int> > &buf,int i) { buf[i].push_back(root->val); if((root->left == nullptr) && (root->right == nullptr)) return ; if((root->left != nullptr) && (root->right != nullptr)) { buf[i + 1].assign(buf[i].begin(),buf[i].end());//开辟新路径 path(root->left,buf,i); path(root->right,buf,i+1); return ; } if(root->left != nullptr) path(root->left,buf,i); if(root->right != nullptr) path(root->right,buf,i); } int main() { TreeNode *root; vector<int> vi = {1,2,4,0,7,0,0,0,3,5,0,0,6,8,0,0,0}; int i = 0; root = CreateBiTree(vi,i);//按先序遍历创建树，遇0为nullptr； vector<vector<int>> travel_path(1000); path(root, travel_path, 0); for(auto &vec:travel_path) { if(vec.empty()) break; for(auto &a:vec) cout << a << " "; cout <<"sum="<< accumulate(vec.begin(), vec.end(),0)<<endl; } }

给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

class Solution { public: /** * * @param root TreeNode类 * @param o1 int整型 * @param o2 int整型 * @return int整型 */ int lowestCommonAncestor(TreeNode* root, int o1, int o2) { if(nullptr == root) return 0; if(o1 == root->val || o2 == root->val) return root->val; int left=lowestCommonAncestor(root->left,o1,o2); int right=lowestCommonAncestor(root->right,o1,o2); if(0 != left && 0 != right) return root->val; return left+right; } };

有感

在分析一颗二叉树时，就是分析 一组双亲和左右孩子 的关系，再通过递归来寻找 满足某个特定条件的 结点的集合，递归以空结点结束。

给定一个二叉树，计算节点值之和最大的路径的节点值之和是多少。这个路径的开始节点和结束节点可以是二叉树中的任意节点 参考：https://blog.csdn.net/linhuanmars/article/details/22969069

class Solution { public: int path(TreeNode* root,int &maxval) { if(nullptr == root) return 0; int left = path(root->left,maxval); int right =path(root->right,maxval); maxval = max(maxval,root->val); maxval = max(maxval,root->val+left); maxval = max(maxval,root->val+right); maxval = max(maxval,root->val+left+right); int val = max(root->val+left,root->val+right); return max(root->val,val); } /** * * @param root TreeNode类 * @return int整型 */ int maxPathSum(TreeNode* root) { if(nullptr == root) return 0; int maxval=root->val; path(root,maxval); return maxval; } };