算法面试5-二叉树和递归

二叉树和递归

例题104：
求一棵二叉树的最高深度

class Solution{
public:
    int maxDepth(TreeNode * root){
        if(root == NULL)
            return 0;
        int leftMaxDepth = maxDepth(root->left);
        int rightMaxDepth = maxDepth(root->right);
        return max(leftMaxDepth,rightMaxDepth) +1；
    }
};

复习二叉树相关的所有操作
例题226：
反转一棵二叉树

/**
 * 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* invertTree(TreeNode* root) {
        if(root == NULL)
            return NULL;
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left,root->right);
        return root;
    }
};

例题100：Same Tree
给出两棵二叉树，判断是否一样

例题101： Symmetric tree
判断一棵二叉树是否是左右对称的

例题222：count Complete Tree Nodes
给定一棵完全二叉树，求完全二叉树的节点个数

例题110 ：
判断一棵二叉树是否为平衡二叉树

例题112：Path Sum

class Solution {
public:
    bool hasPathSum(TreeNode *root,int sum){
        if(root == NULL)
            return sum == 0;
        并列条件判断语句

        if(hasPathSum(root->left,sum-root->val))
            return true;
        if(hasPathSum(root->right,sum-root->val))
            return true;
        return false;
    }
};

如果root的值就等于sum，虽然相等，但是没有root到子结点的路径所以正常应该是返回false

改进的话，改变递归终止条件

class Solution {
public:
    bool hasPathSum(TreeNode *root,int sum){
        if(root == NULL) //根节点root的值为空 直接返回false
            return false;
        if(root->left == NULL && root->right == NULL)//走到最后到达了 ，最终子节点的值和sum做判断
            return root->val == sum;
            //理解更轻松两个条件语句，一个为true则结果为true
        return (hasPathSum(root->left,sum-root->val))||(hasPathSum(root->right,sum-root->val));
        return false;
    }
};

例题404：
求出一棵二叉树所有左叶子的和

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = 0;
        if(root == NULL)
            return 0;

        if(root->left!=NULL&&root->left->left ==NULL &&root->left->right == NULL)
             sum=root->left->val;
        //每当找到一个在最末端的左叶子就去更新sum
        //sumofleftLeaves每次都会使sum获得一次更新
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right) + sum;
    }
};

例题257：
给定一颗二叉树，返回所有表示从根节点到叶子节点路径的字符串

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode * root) {
        vector<string> res;
        if(root == NULL)
            return res;
        if(root->left == NULL && root->right == NULL)
            res.push_back(to_string(root->val));
            return res;
        vector<string> leftS = binaryTreePaths(root->left);
        for(int i = 0;i<leftS.size();i++)
            res.push_back(to_string(root->val)+ "->"+leftS[i]);
        vector<string> rightS = binaryTreePaths(root->left);
        for(int i = 0;i<rightS.size();i++)
            res.push_back(to_string(root->val) + "->"+rightS[i]));

        return res;
    }
};

例题113： Path sum II
例题129：Sum root to leaf numbers

更复杂的递归问题

例题437：Path sum III

class Solution {
public:
    //在以root为根节点的二叉树中寻找和为sum的路径，返回这样的路径个数
    int pathSum(TreeNode * root,int sum){
        if(root == NULL)
            return 0;
        int res = findPath(root,sum);
        res += pathSum(root->left,sum);
        res += pathSum(root->right,sum);
        return res;
    }
private:
    //在以node为根节点的二叉树中，寻找包含node的路径，和为sum
    //返回这样的路径的个数
    int findPath(TreeNode * node,int num){
        if(node == NULL)
            return 0;
        int res = 0;
        if(node->val == num)
            res+=1;
        res += findPath(node->left,num-node->val);
        res += findPath(node->right,num-node->val);
        return res;
    }
};

二分搜索树中的问题

例题235：
给定一棵二分搜索树和两个节点，寻找两个节点的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode * p,TreeNode *q){
        assert(p!= NULL && q!=NULL);
        if(root == NULL) //如果根节点为空，则返回空
            return NULL;
        if(p->val <root->val && q->val<root->val) //p,q都在左侧
            return lowestCommonAncestor(root->left,p,q);
        if(p->val > root->val && q->val>root->val) //p,q都在右侧
            return lowestCommonAncestor(root->right,p,q);  

        return root;      
    }
    }；

例题98:validate binary search tree
给定一棵二叉树，验证是否为二分搜索树
例题450：Delete Node in a BST
给定一棵二分搜索树，删除其中的一个节点
例题230 Kth smallest element in a BST
例题236 lowest ancestor of a binary tree