1.計算給定二叉樹的所有左葉子之和。
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
?? ?int val;
?? ?TreeNode* left;
?? ?TreeNode* right;
?? ?TreeNode(int x)
?? ?{
?? ??? ?val=x;
?? ??? ?left=NULL;
?? ??? ?right=NULL;
?? ?}
};
int findsum(TreeNode* root)
{
?? ?if(root==NULL)
?? ?return 0;
?? ?if(root->left==NULL&&root->right==NULL)
?? ?return 0;
?? ?int leftnum=findsum(root->left);
?? ?if(root->left&&!root->left->left&&!root->left->right)
?? ?{
?? ??? ?leftnum=root->left->val;
?? ?}
?? ?int rightnum=findsum(root->right);
?? ?int sum=leftnum+rightnum;
?? ?return sum;?? ?
}
int main()
{
?? ?TreeNode* root=new TreeNode(1);
?? ?root->left=new TreeNode(2);
?? ?root->right=new TreeNode(3);
?? ?root->left->left=new TreeNode(4);
?? ?root->left->right=new TreeNode(6);
?? ?root->left->right->right=new TreeNode(7);
?? ?root->right->left=new TreeNode(5);
?? ?int sum=findsum(root);
?? ?cout<<sum;
?? ?return 0;
}
思路：首先我們要搞清楚左葉子，即左右子樹的左側葉子結點，特征就是沒有左右孩子，且在父結點的左側，另外在判斷左葉子時我們只能借助于父結點，因為在遍歷到葉子結點時我們無法判斷其是左葉子還是右葉子，在這里我們就用到后序遍歷，通過遞歸函數的返回值來累加求取左葉子數值之和。
當結點為空時，左葉子一定是0，當為葉子結點時左葉子也是0，只有當遍歷到父結點且其含有左葉子時，返回其值。
2.給定一個二叉樹，在樹的最后一行找到最左邊的值。
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
?? ?int val;
?? ?TreeNode* left;
?? ?TreeNode* right;
?? ?TreeNode(int x)
?? ?{
?? ??? ?val=x;
?? ??? ?left=NULL;
?? ??? ?right=NULL;
?? ?}
};
int findValue(TreeNode* root)
{
?? ?queue<TreeNode*> que;
? ? int result=0;
? ? if(root!=NULL)
? ? {
? ? ? ? que.push(root);
? ? }
?? ?while(!que.empty())
? ? {
? ? ? ? int size=que.size();
?? ??? ?for(int i=0;i<que.size();i++)
? ? ? ? {
? ? ? ? ? ? TreeNode* node=que.front();
?? ??? ? ? ?que.pop();
?? ??? ??? ?if(i==0)
?? ??? ??? ?result=node->val;
?? ??? ??? ?if(node->left)
?? ??? ??? ?que.push(node->left);
?? ??? ??? ?if(node->right)
?? ??? ??? ?que.push(node->right);
?? ??? ? }?
?? ?}
?? ?return result;
}
int main()
{
?? ?TreeNode* root=new TreeNode(1);
?? ?root->left=new TreeNode(2);
?? ?root->right=new TreeNode(3);
?? ?root->left->left=new TreeNode(4);
?? ?root->left->right=new TreeNode(6);
?? ?root->left->right->right=new TreeNode(7);
?? ?root->right->left=new TreeNode(5);
?? ?cout<<findValue(root);
?? ?return 0;
}
思路：這道題的左下角的值我們要知道指的是深度最大的那一行的最左側的值，那么其實不找深度最大的一行的第一個元素就行了，因而層序遍歷顯得比較適合。
層序遍歷之前已經提到過就不多贅述了，就只是在此基礎上修改了一小部分，就是取每一層的第一個元素給result，會逐層覆蓋，最終輸出的就是最后一層的第一個元素了。
3.給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目標和。
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
?? ?int val;
?? ?TreeNode* left;
?? ?TreeNode* right;
?? ?TreeNode(int x)
?? ?{
?? ??? ?val=x;
?? ??? ?left=NULL;
?? ??? ?right=NULL;
?? ?}
};
bool isGoal(TreeNode* root,int target)
{
?? ?if(root->left==NULL&&root->right==NULL&&target==0)
?? ?return true;
?? ?if(root->left==NULL&&root->right==NULL&&target!=0)
?? ?return false;
?? ?if(root->left)
?? ?{
?? ??? ?target-=root->left->val;
?? ??? ?if(isGoal(root->left,target))
?? ??? ?return true;
?? ??? ?target+=root->left->val;
?? ? }?
?? ?if(root->right)
?? ?{
?? ??? ?target-=root->right->val;
?? ??? ?if(isGoal(root->right,target))
?? ??? ?return true;
?? ??? ?target+=root->right->val;
?? ?}
?? ?return false;
?? ?
?}?
bool hasPathSum(TreeNode* root,int sum)
{
?? ?if(root==NULL)
?? ?return false;
?? ?return isGoal(root,sum-root->val);
}
int main()
{
?? ?TreeNode* root=new TreeNode(1);
?? ?root->left=new TreeNode(2);
?? ?root->right=new TreeNode(3);
?? ?root->left->left=new TreeNode(7);
?? ?root->left->right=new TreeNode(5);
?? ?cout<<((hasPathSum(root,10)==1)?"true":"false");
?? ?return 0;
}
思路：這里我們可以這樣想，開始遍歷時，將目標值target傳入，如果存在根節點就先用target減去其val值，先遍歷左子樹，此時遍歷到根節點時減去其左子樹的值，之后每遍歷一個左節點就繼續減去它的左子樹的值，直到葉子節點時，如果此時target為0，那么就說明存有路徑和為target，返回true，否則就進行回溯，將target回復原來的值轉而向另外的路徑探索看是否存有這樣的路徑，遍歷右子樹也是如此，注意這里我們如果找到了符合的路徑，但仍未遍歷完整棵樹，也是直接返回true，不必繼續遍歷。
?
