Day.54———树常见算法（长期更新）

喜欢ヅ旅行 2023-03-13 05:54 46阅读 0赞

#### 节点的深度 ####

int maxHeight(TreeNode *root){ 
            if(!root) return 0;
            return max(maxHeight(root->left),maxHeight(root->right))+1;
        }

#### 判断是否为二叉搜索树（左子树小于根，右子树大于根） ####

bool func(TreeNode* root, long long low, long long up)
        { 
            if(!root) return true;
            if(root->val <= low || root->val >= up) return false;
            return func(root->left, low, root->val) && func(root->right, root->val, up);
        }
    
    bool isValidBST(TreeNode* root) { 
            return func(root, LONG_MIN, LONG_MAX);
        }

#### 二叉树两个节点的最近的公共祖先 ####

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
            if (root == nullptr || root == p || root == q) return root;
            
            TreeNode* left = lowestCommonAncestor(root->left, p, q);
            TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
            if (left != nullptr && right != nullptr) { 
                return root;
            }
            return left == nullptr ? right : left;
        }

#### 两棵树是否相同 ####

#### t树是否为s树的子树 ####

bool isSametree(TreeNode* s, TreeNode* t)
        { 
             if(s==NULL && t==NULL) return true;
             return s && t && s->val==t->val && isSametree(s->left, t->left) && isSametree(s->right, t->right);
        }
        
    bool isSubtree(TreeNode* s, TreeNode* t) { 
    	     if(s == NULL)
    	     { 
    	         if(t == NULL) return true;
    	         else return false;
    	     }
    	     return isSametree(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
        }

#### 检查树的平衡性 ####

bool isBalanced(TreeNode* root) { 
            if(!root) return true;
            return abs(maxHeight(root->left) - maxHeight(root->right))  <= 1 ? isBalanced(root->left) && isBalanced(root->right) : false;
        }
        
        //获取节点的最大高度
    int maxHeight(TreeNode *root){ 
        if(!root) return 0;
        return max(maxHeight(root->left),maxHeight(root->right))+1;
    }

#### 二叉树的深度优先遍历DFS ####

void depthFirstSearch(TreeNode* root){ 
        stack<TreeNode*> nodeStack;  //使用C++的STL标准模板库
        nodeStack.push(root);
        TreeNode* node;
        while(!nodeStack.empty()){ 
            node = nodeStack.top();
            printf(format, node->data);  //遍历根结点
            nodeStack.pop();
            if(node->rchild){ 
                nodeStack.push(node->right);  //先将右子树压栈
            }
            if(node->lchild){ 
                nodeStack.push(node->left);  //再将左子树压栈
            }
        }
    }

#### 二叉树的广度优先（层级）遍历BFS ####

void breadthFirstSearch(Tree root){ 
        queue<Node *> nodeQueue;  //使用C++的STL标准模板库
        nodeQueue.push(root);
        Node *node;
        while(!nodeQueue.empty()){ 
            node = nodeQueue.front();
            nodeQueue.pop();
            printf(format, node->data);
            if(node->lchild){ 
                nodeQueue.push(node->lchild);  //先将左子树入队
            }
            if(node->rchild){ 
                nodeQueue.push(node->rchild);  //再将右子树入队
            }
        }
    }

#### 前序遍历、中序遍历、后序遍历 ####

点击[参考文章][Link 1]

#include<iostream>
    #include<vector>
    #include<stack>
    #include<queue>
     
     
    using namespace std;
    struct TreeNode{ 
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    	TreeNode(int v) :val(v), left(NULL), right(NULL){ }
    };
     
     
     
     
    //------------------树的前序遍历：根-左-右------------------------------
    //---------------------递归法-------------------------------------------
     
    vector<int> preorderTraversal_recursive(TreeNode *root, vector<int> &res)
    { 
     
    	if (root == nullptr)
    		return res;
    	else
    	{ 
    		res.push_back(root->val);
    		preorderTraversal_recursive(root->left,res);
    		preorderTraversal_recursive(root->right,res);
    		return res;
    	}
     
    }
     
     
    //-----------------------非递归法-------------------------------------
    vector<int> preorderTraversal_iteratively(TreeNode *root)
    { 
    	vector<int> res;
    	if (root == nullptr)
    	{ 
    		return res;
    	}
    	stack<TreeNode *> st;
    	st.push(root);
    	while (!st.empty())
    	{ 
    		TreeNode *node = st.top();
    		st.pop();
    		res.push_back(node->val);
    		
    		if (node->right)
    			st.push(node->right);
    		if (node->left)
    			st.push(node->left);
    			
    	}
    	return res;
    }
     
     
    //-------------------------树的中序遍历：左-根-右---------------------------
     
    //-----------------------------递归法---------------------------------------
    //这是本质一种:以<最左边线>为主干，将最<左边>上的节点压入栈，以这些节点为线索,遍历整棵树的方式。
    vector<int> inorderTraversal_recursive(TreeNode *root, vector<int> &res)
    { 
    	if (root == nullptr)
    		return res;
    	else
    	{ 
    		inorderTraversal_recursive(root->left, res);
    		res.push_back(root->val);
    		inorderTraversal_recursive(root->right, res);
    		return res;
    	}
    }
     
     
    //-----------------------------非递归法---------------------------------------
    vector<int> inorderTraversal_iteratively(TreeNode *root)
    { 
    	vector<int> res;
    	if (root == nullptr)
    		return res;
    	stack<TreeNode *> st;
     
    	TreeNode *node = root;
    	while (!st.empty()|| node)
    	{  
    		
    		while (node)
    		{ 
    			st.push(node);
    			node = node->left;
    		}
    		if (!st.empty())
    		{ 
    			node = st.top();
    			res.push_back(node->val);
    			st.pop();
    			node = node->right;
    		}
    	}
    	return res;
    }
     
     
     
    //-------------------------树的后序遍历：左-右-根--------------------------------
    //-----------------------------------递归法--------------------------------------
    vector<int>  postorderTraversal_recursive(TreeNode *root, vector<int> &res)
    { 
    	if (root == nullptr)
    		return res;
    	else
    	{ 
    		
    		postorderTraversal_recursive(root->left, res);
    		postorderTraversal_recursive(root->right, res);
    		res.push_back(root->val);
    		return res;
    	}
    }
     
     
     
    //-----------------------------非递归法---------------------------------------
    vector<int> postorderTraversal_iteratively(TreeNode *root)
    { 
    	vector<int>res;
    	if (root == nullptr)
    		return res;
    	stack<TreeNode *>st;
    	st.push(root);
    	while (!st.empty())
    	{ 
    		TreeNode *node = st.top();
    		st.pop();
    		res.push_back(node->val);
    		if (node->left)
    		{ 
    			st.push(node->left);
    		}
    		if (node->right)
    		{ 
    			st.push(node->right);
    		}
    	}
    	reverse(res.begin(), res.end());
    	return res;
    }
     
     
     
     
    //-------------------------------------树的层次遍历--------------------------
     
    vector<int> levelorderTraversal(TreeNode *root)
    { 
    	vector<int>res;
    	if (root == nullptr)
    		return res;
    	queue<TreeNode *>que;
    	que.push(root);
    	while (!que.empty())
    	{ 
    		TreeNode * node = que.front();
    		que.pop();
    		res.push_back(node->val);
    		if (node->left)
    			que.push(node->left);
    		if (node->right)
    			que.push(node->right);
    	}
    	return res;
    }
     
    int main()
    { 
    	struct TreeNode *root = new TreeNode(1);
    	root->left = new TreeNode(2);
    	root->right = new TreeNode(3);
    	root->right ->left= nullptr;
    	root->right->right = nullptr;
    	root->left->left = new TreeNode(4);
    	root->left ->right= new TreeNode(5);
     
    	vector<int>res;
     
    	cout << "树的前序遍历：递归版" << endl;
    	preorderTraversal_recursive(root,res);
    	for (int i = 0; i < res.size(); i++)
    	{ 
    		cout << res[i] << " ";
    	}
    	cout << endl;
     
    	
    	cout << "树的前序遍历：迭代版" << endl;
    	res = preorderTraversal_iteratively(root);
    	for (int i = 0; i < res.size(); i++)
    	{ 
    		cout << res[i] << " ";
    	}
    	cout << endl<<endl;
     
    	res.clear();
    	cout << "树的中序遍历：递归版" << endl;
    	inorderTraversal_recursive(root, res);
    	for (int i = 0; i < res.size(); i++)
    	{ 
    		cout << res[i] << " ";
    	}
    	cout << endl;
     
     
    	cout << "树的中序遍历:迭代版" << endl;
    	res=inorderTraversal_iteratively(root);
    	for (int i = 0; i < res.size(); i++)
    	{ 
    		cout << res[i] << " ";
    	}
    	cout << endl<<endl;
     
     
    	res.clear();
    	cout << "树的后序遍历：递归版" << endl;
    	postorderTraversal_recursive(root, res);
    	for (int i = 0; i < res.size(); i++)
    	{ 
    		cout << res[i] << " ";
    	}
    	cout << endl;
     
     
    	cout << "树的后序遍历：迭代版" << endl;
    	res = postorderTraversal_iteratively(root);
    	for (int i = 0; i < res.size(); i++)
    	{ 
    		cout << res[i] << " ";
    	}
    	cout << endl << endl;
     
     
     
    	cout << "树的层次遍历:" << endl;
    	res = levelorderTraversal(root);
    	for (int i = 0; i < res.size(); i++)
    	{ 
    		cout << res[i] << " ";
    	}
    	cout << endl << endl;
    	return 0;
    }

[Link 1]: https://blog.csdn.net/qq_27962497/article/details/82191807?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522158864771319725222414385%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=158864771319725222414385&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-3