【算法day13】二叉树：递归与回溯

题目引用

找树左下角的值
路径总和
从中序与后序遍历构造二叉树

今天就简简单单三道题吧~

1. 找到树左下角的值

给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

我们来分析一下题目，最底层的叶子节点，所以我们要求出树的深度，并且进行判断他是否到达底层。首先我们定义一个全局变量res和全局变量maxDep来记录递归过程中更深的节点和更深节点的值。然后我们判断当前节点有没有左右孩子节点，如果有我们递归进那个节点并更新res和maxDep，同时定义局部变量depth将其++后传进下一层，当其操作完返回这一层时将depth--，用作向右孩子递归的参数。而这个过程就叫做回溯。
我们来看代码

int res;
    int maxDep=INT_MIN;
    void travisal(TreeNode* root,int depth){
        if(root->left==NULL&&root->right==NULL){
            if(depth>maxDep){
                maxDep=depth;
                res=root->val;
            }
            return;
        }

        if(root->left){
            depth++;
            travisal(root->left,depth);
            depth--;
        }

        if(root->right){
            depth++;
            travisal(root->right,depth);
            depth--;
        }
    }
    int findBottomLeftValue(TreeNode* root) {
        travisal(root,0);
        return res;
    }

2.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

我们来看题目，这道题其实知道了原理就和上道题大差不差了。上一道题目是找到最底层的节点的值，而这一道题目是找到一条相加为0的路径，两道题目都需要我们在二叉树中一层一层的寻找符合条件的节点并且返回它，那么我们是不是不难写出这样的模版

看情况返回类型 traversal(TreeNode* root,//第二变量用于判断){
        //对每一个节点要做的操作

        if(root->left){
            //增加条件
            //递归左边
            //减少条件
        }
        if(root->right){
            //增加条件
            //递归右边
            //减少条件
        }

        //考虑是否返回
    }

那么我们在这道题就将相加改为一开始就有一个变量等于targetSum，逐层减去每个节点的val，一旦==0，就返回true。
来看代码：

bool traversal(TreeNode* root,int count){
        if(!root->left&&!root->right&&count==0) return true;
        if(!root->left&&!root->right) return false;

        if(root->left){
            count-=root->left->val;
            if(traversal(root->left,count)) return true;
            count+=root->left->val;
        }
        if(root->right){
            count-=root->right->val;
            if(traversal(root->right,count)) return true;
            count+=root->right->val;
        }

        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==NULL) return false;
        return traversal(root,targetSum-root->val);
    }

大家看，一旦我们整理出规律，是不是这类题目我们只要考虑细节条件就能迎刃而解呢？

3.从中序与后序遍历构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

这道题目我们在学习数据结构时就做过，现在只要模拟过程就能解决啦。直接看代码

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 delimitIndex;
        for(delimitIndex=0;delimitIndex<inorder.size();delimitIndex++){
            if(inorder[delimitIndex]==rootValue) break;
        }

        vector<int> leftInorder(inorder.begin(),inorder.begin()+delimitIndex);
        vector<int> rightInorder(inorder.begin()+delimitIndex+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);
    }