14,.左下角的值，路径和，由序列确定树

找树左下角的值

迭代法

• 层序遍历

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> qu;qu.push(root);TreeNode* left=qu.front();while(!qu.empty()){int sz=qu.size();left=qu.front();for(int i=0;i<sz;i++){TreeNode* cur=qu.front();qu.pop();if(cur->left)qu.push(cur->left);if(cur->right)qu.push(cur->right);}}return left->val;}
};

递归法

• 先序遍历，记录深度最深的。

class Solution {
public:int preorder(TreeNode* root,int depth,int& maxDep){if(!root)return 0;depth++;if(!root->left&&!root->right){if(depth>maxDep){maxDep=depth;return root->val;}else{return -1;}}int le=-1,ri=-1;if(root->left){le=preorder(root->left,depth,maxDep);}if(root->right){ri=preorder(root->right,depth,maxDep);}if(ri==-1)ri=le;return ri;}int findBottomLeftValue(TreeNode* root) {int maxDep=0;return preorder(root,0,maxDep);}
};

路径总和

递归

class Solution {
public:bool preorder(TreeNode* root,int sum,int tar){sum+=root->val;if(!root->left&&!root->right){if(sum==tar)return 1;return 0;}int left=0,right=0;if(root->left)left=preorder(root->left,sum,tar);if(root->right)right=preorder(root->right,sum,tar);return left||right;}bool hasPathSum(TreeNode* root, int targetSum) {if(!root)return 0;return preorder(root,0,targetSum);}
};

迭代

class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {stack<int> numst;stack<TreeNode*> st;if(!root)return 0;st.push(root);numst.push(root->val);while(!st.empty()){TreeNode* cur=st.top();st.pop();int cur_sum=numst.top();numst.pop();if(!cur->left&&!cur->right){if(cur_sum==targetSum)return 1;}if(cur->right){st.push(cur->right);numst.push(cur_sum+cur->right->val);}if(cur->left){st.push(cur->left);numst.push(cur_sum+cur->left->val);}}return 0;}
};

变体题

迭代和递归思路差不多

class Solution {
public:vector<vector<int>> pathSum(TreeNode* root, int targetSum) {stack<int> numst;stack<vector<int>> vst;vector<vector<int>> res;stack<TreeNode*> st;if(!root)return res;st.push(root);vector<int> roo;roo.push_back(root->val);vst.push(roo);numst.push(root->val);while(!st.empty()){TreeNode* cur=st.top();st.pop();int cur_sum=numst.top();numst.pop();vector<int> cur_v=vst.top();vst.pop();if(!cur->left&&!cur->right){if(cur_sum==targetSum){res.push_back(cur_v);}}vector<int> tmp=cur_v;if(cur->right){st.push(cur->right);numst.push(cur_sum+cur->right->val);cur_v.push_back(cur->right->val);vst.push(cur_v);}cur_v=tmp;if(cur->left){st.push(cur->left);numst.push(cur_sum+cur->left->val);cur_v.push_back(cur->left->val);vst.push(cur_v);}}return res;}
};

由序列构造二叉树

中序与后序

class Solution
{
public:TreeNode *build(vector<int>& inorder, vector<int>& postorder){if (inorder.empty())return nullptr;int val = postorder[postorder.size() - 1];TreeNode *root = new TreeNode(val);vector<int>::iterator it = std::find(inorder.begin(), inorder.end(), val);if(it==inorder.end())return nullptr;vector<int> left(inorder.begin(), it++);vector<int> right(it, inorder.end());postorder.pop_back();root->right = build(right, postorder);root->left = build(left, postorder);return root;}TreeNode *buildTree(vector<int>& inorder, vector<int>& postorder){return build(inorder,postorder);}
};

前序与中序

可以轻松写成类似代码

class Solution {
public:int count=0;TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.empty()||inorder.empty())return nullptr;int val=preorder[count++];auto it=find(inorder.begin(),inorder.end(),val);TreeNode* root=new TreeNode(val);vector<int> left(inorder.begin(),it);vector<int> right(++it,inorder.end());root->left=buildTree(preorder,left);root->right=buildTree(preorder,right);return root;}
};