LeetCode 513. 找树左下角的值
思路：
采用递归法需要找到最大深度，最大深度的第一个值就是要返回的值,求最大深度的过程中需要递归与回溯相互配合
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxdepth=0;
int result;
void depthget(TreeNode* pointer,int depth)
{
if(pointer->left==0&&pointer->right==0)
{
if(depth>maxdepth)
{
maxdepth=depth;
result=pointer->val;
}
}
if(pointer->left!=NULL)
{
depth++;
depthget(pointer->left,depth);
depth--;
}
if(pointer->right!=NULL)
{
depth++;
depthget(pointer->right,depth);
depth--;
}
return ;
}
int findBottomLeftValue(TreeNode* root) {
depthget(root,1);
return result;
}
};
LeetCode 112. 路径总和
思路：
这道题也采用了回溯，方法和上一题类似，每遍历一次就让目标值减去当前的值，再向下遍历，如果在最后一层中目标值为0了就返回true，同时在回溯的时候每层都返回true。113的解法类似。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool getnum(TreeNode* pointer,int count)
{
if(pointer->left==NULL && pointer->right==NULL && count==0)
{
return true;
}
if(pointer->left==NULL &&pointer->right ==NULL)
{
return false;
}
if(pointer->left!=NULL)
{
count-=pointer->left->val;
if(getnum(pointer->left,count)) return true;
count+=pointer->left->val;
}
if(pointer->right!=NULL)
{
count-=pointer->right->val;
if(getnum(pointer->right,count)) return true;
count+=pointer->right->val;
}
return false;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==NULL) return false;
return getnum(root,targetSum-root->val);
}
};
LeetCode 106. 从中序与后序遍历序列构造二叉树
思路：
中序的顺序是左中右，后序的顺序是左右中，所以后序的最后一个节点就是根节点，这样的话中序中根节点的左边就是左子树，右边就是右子树，同理可得在后序中右子树的那些数值里面，最后一个就是右子树的根节点。按照这个规则就能得到二叉树。这个过程分为几步：1、如果后序数组为空，则说明是空节点；2、如果不为空，那么取后序数组最后一个元素作为节点元素；3、找到后序数组最后一个元素在中序数组的位置，作为切割点；4、切割中序数组，切成中序左数组和中序右数组 （一定是先切中序数组）；5、切割后序数组，切成后序左数组和后序右数组；6、递归处理左区间和右区间。105题采用的方法也是一致的。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* traversal (vector<int>& inorder, vector<int>& postorder)
{
if(postorder.size()==0) return NULL;
//找到根节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
//叶子节点
if (postorder.size() == 1) return root;
//分割中序遍历
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
//划分左右子树
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
//舍弃确定的根节点
postorder.resize(postorder.size() - 1);
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
};
