二叉树常见算法

# DFS

原来前/中/后序遍历都属于dfs啊 😃

对于二叉树的题目,其要么在从上往下的 "递" 过程进行判断,要么在从下往上的 "归" 过程操作

dfs模板
dfs(node){
    fun(node);
    dfs(node->left);
    dfs(node->right);
    ans=xx;
    return ;
}

//二叉树dfs前序遍历的迭代实现
void dfs(root){
    stk.push(root);
    while(!stk.empty()){
        cur=stk.top();
        stk.pop();
        fun(cur);
        stk.push(cur->right);
        stk.push(cur->left);
    }
}
//中序
//优先向左访问,一直到空节点时,才从栈中取出一个节点并操作
//然后尝试向右访问,在向右访问时,访问一个节点,就再把它当作根节点再次操作
void dfs(root){
	while(!stk.empty()&&cur){
        while(cur){
            stk.push(cur);
            cur=cur->left;
        }
        cur=stk.top();
        skt.pop();
        cur=cur->right;
    }
}

671. 二叉树中第二小的节点

问题转化为寻找大于根节点的最大节点 ,主要用来学习lamda函数

考虑剪枝操作 ,因为下面的值是越来越大的,所以用当前值更新过后后面就没必要遍历了

112. 路径总和

//1.递归 ,PathSum(TreeNode* root, int targetSum) 表示从root出发是否有和为root的路径
只需判断是否有从left/right出发和为sum-node->val的路线
故递推式: PathSum(root,Sum)=Path(root->left,Sum-root->val)||Path(root->right,Sum-root->val)
//2.BFS
BFS 使用 队列 保存遍历到每个节点时的路径和，如果该节点恰好是叶子节点，并且 路径和 正好等于 sum，说明找到了解

129. 求根节点到叶节点数字之和

//同理,考虑递归遍历与bfs
1.前序遍历
  若当前节点为叶子节点, 将其和加到sum
  否则 将当前值继续传递给叶子节点 
2.bfs

199. 二叉树的右视图

//使用后序遍历 ,由后序遍历的那个图可知 ,每层最后一次访问的为最右侧结点
function<void(TreeNode*, int)> fun = [&](TreeNode* node, int depth) {
            //利用后序遍历的那个图可知,每层最后一次遍历到的为最右边的节点
            if (!node) return;
            if (depth >= ans.size()) {  // 动态扩展 ans
                ans.resize(depth + 1);
            }
            fun(node->left, depth + 1);
            fun(node->right, depth + 1);
            ans[depth] = node->val; 
        };
//也可以使用 根右左的方法,每层第一个遍历到的是最右侧节点
function<void(TreeNode*, int)> fun = [&](TreeNode* node, int depth) {
            //利用后序遍历的那个图可知,每层最后一次遍历到的为最右边的节点
            if (!node) return;
            if (depth == ans.size()) {  // 动态扩展 ans
                ans.push_back(node->val);
            
            fun(node->right, depth + 1);
            fun(node->left, depth + 1);
        };

1448. 统计二叉树中好节点的数目

//BFS 记录路径上的最大值,比较即可
function<void(TreeNode*,int)> fun=[&](TreeNode* node,int lmax){
            if(!node) return ;
            if(node->val>=lmax) ans++;
            lmax=max(lmax,node->val);
            fun(node->left,lmax);
            fun(node->right,lmax);
        };

1457. 二叉树中的伪回文路径

//很深刻的一题 ,对回溯的应用
1.对于伪回文的判断,要求元素的出现次数满足 0/1奇 多偶,因此只需要记录每条路上元素的出现情况即可
2.在记录路上的情况时,要注意回溯
        dfs=[&](TreeNode* node){
            if(!node) return ;
            count[node->val]++;
            if(!node->left&&!node->right) check();

            dfs(node->left);
            dfs(node->right);
            count[node->val]--;//在遍历完左右子树后撤销对当前节点的遍历,使其在递归返回父节点时保持原样
        };

1315. 祖父节点值为偶数的节点和

非常无脑,dfs即可

988. 从叶结点开始的最小字符串

string smallestFromLeaf(TreeNode* root){
    //暴力写法,自顶向下遍历,记录当前节点到根节点的路径字符串,当遍历到叶子节点时,和答案比较即可
    string ans="~";
    function<void(TreeNode*,string)> dfs;
    dfs=[&](TreeNode* node,string path){
        //path:当前节点到根节点的路径
        char ch=node->val+'a';
        path=ch+path;
        if(!node->left&&!node->right) ans=min(ans,path);
        if(node->left) dfs(node->left,path);
        if(node->right) dfs(node->right,path);
    };
    dfs(root,"");
    return ans;
}

1026. 节点与其祖先之间的最大差值

    int maxAncestorDiff(TreeNode* root) {
        //祖先:在同一条路径上  问题转化为找到同一条路径上的最大/小值,计算差值即可
        int ans=0;
        function<void(TreeNode*,int,int)> dfs;
        dfs=[&](TreeNode* node,int mx,int mn){
            if(!node) ans=max(ans,mx-mn);
            mx=max(mx,node->val);
            mn=min(mn,node->val);
            dfs(node->left,mx,mn);
            dfs(node->right,mx,mn);
        };
        dfs(root,0,root->val);
        return ans;
    }

100. 相同的树

bool isSameTree(TreeNode* p, TreeNode* q) {
        //自上往下(dfs)和自下往上(递归)都可以
        bool flag=true;
        function<void(TreeNode*,TreeNode*)> dfs;
        dfs=[&](TreeNode* node1,TreeNode* node2){
            if(node1&&node2){//两节点值都存在时,比较节点值
                if(node1->val!=node2->val) {flag=false;return ;}
                dfs(node1->left,node2->left);
                dfs(node1->right,node2->right);
            }
            if(!node1&&!node2) return ;//二者都为空节点时,不操作
            flag=false;                //只有一个节点存在,返回false
        };
        dfs(p,q);
        return flag;
    }

    bool isSameTree(TreeNode* p, TreeNode* q) {//判断以p,q为根节点的两棵树是否相同
        //采用递归实现
        if(!p&&!q) return true;//均为空节点,true
        if(!p&&q||!q&&p) return false;
        if(p->val!=q->val) return false;//终止条件,当只有一个节点或节点值不同时,退出
        return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }

101. 对称二叉树

bool isSymmetric(TreeNode* root) {
        //自上向下遍历dfs(迭代)
        bool flag=true;
        function<void(TreeNode*,TreeNode*)> dfs;
        dfs=[&](TreeNode* t1,TreeNode* t2){
            //比较t1和t2是否轴对称
            if(!t1||!t2) flag=(t1==t2);
            if(t1->val!=t2->val) flag=false;//两个节点,判断是否相等
  			dfs(t1->left,t2->right);
            dfs(t1->right,t2->left);
        };
        dfs(root->left,root->right);
        return flag;
    }

	//递归,判断t1和t2两棵树是否对称
bool isSymmetric(TreeNode* t1,TreeNode* t2) {
    if(!t1||!t2) return t1==t2;//当一个空节点时false,2个空节点时true,0个时不会进入该判断
    if(t1->val!=t2->val) return false;//两个节点,判断是否相等
    return isSymmetric(t1->left,t2->right)&&isSymmetric(t1->right,t2->left);
}

951. 翻转等价二叉树

    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        //递归, 如果两棵树的左右子树等价,且这两棵树根节点相同,则这两棵树等价
        if(!root1||!root2) return root1==root2;
        if(root1->val!=root2->val) return false;//判断根节点是否相同
        return flipEquiv(root1->left,root2->left)&&flipEquiv(root1->right,root2->right)||
        flipEquiv(root1->left,root2->right)&&flipEquiv(root1->right,root2->left);
    }

找出克隆二叉树中的相同节点

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        //两棵树同时遍历,比较original节点与target,二者相同时返回cloned,因为二者同步所以进行一次前序遍历即可
        if(!original) return NULL;
        if(original==target) return cloned;
        TreeNode* lnode=getTargetCopy(original->left,cloned->left,target);
        TreeNode* rnode=getTargetCopy(original->right,cloned->right,target);
        return lnode==NULL?rnode:lnode;
    }

226. 翻转二叉树

814. 二叉树剪枝

/*一道非常有意思的题,巧妙地用返回的node判断root树的子树是否有1   同样巧妙的还有判断平衡二叉树,当不平衡时返回-1;*/
是否需要删除子树?--子树中没有1即可

1325. 删除给定值的叶子节点

跟上一题一样,最后的返回条件改一下即可,返回null表示该树需要删除,否则不需要删除
TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if(!root) return nullptr;
        TreeNode* lnode=removeLeafNodes(root->left,target);
        TreeNode* rnode=removeLeafNodes(root->right,target);
        if(!lnode) root->left=nullptr;
        if(!rnode) root->right=nullptr;
        if(!root->left&&!root->right&&root->val==target) return nullptr;
   		//该节点为叶子且值为target时,返回null,表示该树需要删除
        else return root;//否则返回root
}

1110. 删点成林

如果当前节点被删除，那么就检查左/右孩子 是否被删除，如果没被删除，就加入答案
如果当前节点被删除，返回空节点，否则返回当前节点

# 回溯

每次执行完一次函数后,都会恢复到进入函数之前的状态,此乃回溯之法 ⏲️

257. 二叉树的所有路径

//1.使用临时变量,表示当前路径0.上的字符串
vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        function<void(TreeNode*,string)> dfs;
        dfs=[&](TreeNode* node,string path){
            if(!node) return ;
            path+=to_string(node->val);
            if(!node->left&&!node->right){
                ans.push_back(path);
                return ;
            }
            path+="->";
            dfs(node->left,path);
            dfs(node->right,path);
        };
        dfs(root,"");
        return ans;
    }
//2.回溯,使用外部变量,记录当前的路径
    dfs = [&](TreeNode* node) {
        if (!node) return;
        int old_len = path.size();
        path += to_string(node->val);
        if (!node->left && !node->right) {
            ans.push_back(path);
            path.resize(old_len);
            return;
        }
        path += "->";
        dfs(node->left);
        dfs(node->right);
        // 回溯
        
        path.resize(old_len);//因为函数每执行一次就回溯一次,故回溯完的结果是上一层刚执行完的结果,即认为当前字符并未添加
    };

113. 路径总和 II

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        vector<vector<int>> ans;
        int sum=0;
        function<void(TreeNode*)> dfs;
        dfs=[&](TreeNode* node){
            if(!node) return ;
            sum+=node->val;
            path.push_back(node->val);
            if(!node->left&&!node->right&&sum==target) ans.push_back(path);
            dfs(node->left);//执行完不会影响path的值,因为其结束后会恢复到进入之前的状态
            dfs(node->right);
            sum-=node->val;//每次执行完一次函数后,都会恢复到进入函数之前的状态,此乃回溯之法
            path.pop_back();
        };
        dfs(root);
        return ans;
    }

437. 路径总和 III

//对于一般的二叉树的回溯, 其关键词在于 同一条路径
//利用前缀和记录这条路径上的根节点路径和

# 最近公共祖先

//关键在于找到 p,q,ans 三个点的关系 ,最终ans点一定满足 左右各含一个p/q;
//从下往上在回溯的过程中判断,故只能使用后序遍历,从子树中传递
TreeNode* fun(TreeNode* root,p,q) {
    //判断root树中是否含有p/q/ans ,若有,则返回 p/q/ans
    if(!root||root==p||root==q) return root;
    lnode=fun(root->left,p,q);	//在左子树中寻找
    rnode=fun(root->right,p,q); //在右子树中寻找
    if(lnode&&rnode) return root;//左右各一个,一定是答案点
    if(lnode) return rnode;
    return lnode;
}
//对于 搜索树
更改最终ans的判定条件即可  ans一定满足 p<root<q 且ans
TreeNode* fun(TreeNode* root,p,q){
    int cur=root->val;
        if(cur>p->val&&cur>q->val) return fun(root->left,p,q);
        if(cur<p->val&&cur<q->val) return fun(root->right,p,q);
        return root;
}

98. 验证二叉搜索树

bool isValidBST(TreeNode* root){
    //"递"的思想,按照中序遍历,判断是否为递增即可
    if(!isbst(root->left)) return false;
    if(root->val<=pre) return false;
    pre=root->val;//更新pre的值
    return isbst(root->right);
}

bool isBST(TreeNode* root,int mn,int mx){
    //前序遍历,根据bst的定义来
    //按照前序遍历构建bst的过程来看,在添加每个节点时,其只需满足一定范围即可,故思路就是将这个范围逐渐往下传递,判断每个节点是否满足条件	若当前为左,其必须小于父节点,**且受到祖先的限制**  若为右,其必须大于父节点,**且受到祖先的限制**
    if(!root) return true;
    int cur=root->val;
    return cur>mn&&cur<mx
        &&isbst(root->left,mn,cur)
        &&isbst(root->right,cur,mx);
}

# BFS

//每一层XXX ,此时que中存储一整行的元素,每次都处理一行
while(!que.empty()){
    int n=que.siz();
    for(int i=.;i<n;i++){
        node=que.front();
        que.pop();
        if(node->left) que.push(node->left);
        if(node->right) que.push(node->right);
    }
    
}

515. 在每个树行中找最大值

//que每次存储一行元素,每次操作都处理一行而不是一个
如何判断下一层??---for循环执行完就表示当前层遍历完

2415. 反转二叉树的奇数层

/*方法1 bfs
记录当前访问的层数,若为奇数层就记录当前层的所有数值,反序赋值(利用栈与队列)

方法2 dfs
两颗 对称二叉树的思想,根左右和根右左 同时遍历恰好能得到对称位置,若当前层为奇数,就交换二者数值*/
dfs_swap=[&](TreeNode* node1,TreeNode* node2,int is_odd){
    		//对于对称节点node1和node2,若当前层为奇数就交换二者
            if(!node1) return ;
            if(is_odd){
                int temp=node1->val;
                node1->val=node2->val;
                node2->val=temp;
            }
            dfs_swap(node1->left,node2->right,is_odd^1);
            dfs_swap(node1->right,node2->left,is_odd^1);
        };

# 二叉搜索树

bro觉得最

# 递归

222. 完全二叉树的节点个数

判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子

110. 平衡二叉树

/*最小不平衡树的左右高度差>1,故可以

平衡二叉树

对于所有的不平衡二叉树,其一定会有这样的最小不平衡部分

654. 最大二叉树

404. 左叶子之和

/*对于一个节点,是无法通过它自身来判断其是否为左叶子的,所以只能通过父节点来判断其左孩子是否为叶子.

# DFS

# 回溯

# 最近公共祖先

# BFS

# 二叉搜索树

# 递归

网格图算法