当前位置：首页 > article >正文

代码随想录二刷|二叉树7

article 2025/2/5 1:16:07

二叉树

理论基础

二叉树是有向图

路的长度用边的个数计算，但是力扣一般用点个数算

顶点深度：根节点到顶点的最短路长度

顶点高度：顶点到叶子顶点的最短有向路长度的最大值（顶点到最远的的叶子的路径长度）

树的高度：根顶点高度

1、满二叉树

只有出度为0的点和出度为2的点，不切所有出度为0的点都在最后一层

高度为n的满二叉树有 $2^{n+1}-1$ 个顶点

2、完全二叉树

除了最后一层可能没有填满之外，所有层都填满，并且最后一层的顶点都在左边

也就是叶子顶点都在倒数第二层和倒数第一层，倒数第二层的叶节点在同一层内部顶点的右边，如果倒数第二层有出度为1的点那么它一定有左儿子

高度为n的完全二叉树有 $2^{n},2^{n+1}-1]$ 个顶点

3、二叉搜索树（二叉排序树）

有三个条件

（1）如果左子树不空，那么左子树的所有元素都小于根顶点

（2）如果右子树不空，那么右子树的所有元素都大于根顶点

（3）左右子树都是二叉搜索树

4、平衡二叉搜索树

是二叉搜索树，并且左右两颗子树的高度差小于等于1，左右子树也是平衡二叉搜索树

5、二叉树的存储

（1）链表

节点的定义：

struct Node{
	int val;
	 Node * left;
	 Node* right;
	Node(int x):val(x),left(NULL),right(NULL){}
};

（2）数组

第i层第j个： $2^{i-1}+j-1$

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

（代码随想录）

6、遍历方式

（1）深度优先

1）前序遍历：中左右

2）中序遍历：左中右

3）后序遍历：左右中

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

前序：从根节点出发，根节点-左子树-右子树，在左子树中也按照根节点-左子树-右子树的次序，最后是最右边的叶子；

中序：从最左边的叶节点出发，按照左儿子-父亲-右儿子的次序，然后刚才得父亲作为左儿子继续遍历，最后是根节点的右儿子；

（左子树遍历到4，4作为左儿子，下一个是5，然后右儿子是右子树，7-6-8）

后序：从最左边的叶节点出发，按照左儿子-右儿子-父亲次序，整个左子树作为新的左儿子，去遍历右子树，最后是根节点；

（2）广度优先

层次遍历（迭代法）

深度优先遍历法

递归遍历

前序遍历

void traversal(Node * x,vector<int>&vec){
	if(x==NULL)return ;
	vec.push_back(x->val);
	traversal(x->left,vec);
	tracersal(x->right,vec);
}
vector<Node*>preorder(Node* root){
	vector<int>vec;
	traversal(root,vec);
	return vec;
}

中序遍历

void traversal(Node * x,vector<int>&vec){
	if(x==NULL)return ;
	
	traversal(x->left,vec);
	vec.push_back(x->val);
	tracersal(x->right,vec);
}
vector<int>inorder(Node* root){
	vector<int>vec;
	traversal(root,vec);
	return vec;
}

后序遍历

void traversal(Node * x,vector<int>&vec){
	if(x==NULL)return ;
	traversal(x->left,vec);
	tracersal(x->right,vec);
	vec.push_back(x->val);
}
vector<int>backorder(Node* root){
	vector<int>vec;
	traversal(root,vec);
	return vec;
}

迭代遍历

（如果终止条件只有栈空，那么一开始要让root入栈，否则一开始不让root入栈）

要解决两个问题：访问和处理

访问都是从根节点开始，先访问左边，前中后序的访问都是这样；处理是将元素放进结果数组的，处理是前序/中序/后序的

前序遍历

因为前序遍历的处理次序和访问次序一样，都是从根节点开始的，所以处理和访问同时进行

因为右边后处理，所以右边先进栈

vector<int> preorder(Node* root){
	vector<int>res;
	stack<Node*>st;
	st.push(root);
	while(!st.empty()){
		Node* now=st.top();
		res.push(now->val);
		st.pop();
		if(now->right!=NULL)st.push(now->right);
		if(now->left!=NULL)st.push(now->left);
		
	}
	return res;
}

中序遍历

用指针访问，用栈处理

访问：

指针每次先存到栈中，再向左移动，如果遇到空指针，说明找到了叶子，应该想办法去处理了（因为是左中右的顺序处理）,

处理：

指针遇到空，开始处理，取栈顶元素为cur，并弹出，栈顶元素加入数组，指针向右移动

找到叶子以后，指针移动到叶子的父亲，开始处理父亲，处理父亲以后进入右子树
因为是先进栈后移动指针，所以叶子没有被放进栈

终止条件：

访问和处理都结束，也就是指针为空且栈为空

vector<int>inorder(Node* root){
	vector<int>res;
	stack<Node*> st;
	Node* cur=root;
	
	while(!st.empty()||cur!=NULL)	{
		if(cur==NULL){
			cur=st.top();
			st.pop();
			res.push_back(cur->val);
			cur=cur->right
		}else{
			st.push(cur);
			cur=cur->left;
			
		}
	}
	return res;
}

后序遍历

先在访问的同时按照按照中右左处理，反转结果数组

vector<int> backorder(Node* root){
	vector<int>res;
	stack<Node*> st;
	st.push(root);
	while(!st.empty()){
		Node* now=st.top();
		res.push_back(now->val);
		st.pop();				if(now->left!=NULL)st.push(now->left);
		if(now->right!=NULL)st.push(now->right);		
	}
	reverse(res.begin(),res.end())
	return res;
}

统一迭代法:统一前中后序的迭代

栈的元素类型改成键值对，键是节点指针，值表示是否访问过

每次取栈顶并弹出，判断是否访问过栈顶，如果初次访问，就访问它，将他的儿子放入栈，将他的状态改为true并放入栈；如果已经访问过，那么就进行处理，将他放进结果数组，并且弹出

三种迭代的区别在于顶点和他的儿子进入栈的次序，（先入栈会后处理）

前序遍历：中左右顺序处理，所以右儿子先入，左儿子再入，自己最后

中序遍历：左中右顺序处理，所以右儿子先入，自己再入，左儿子最后

后序遍历：左右中顺序遍历，所以自己先入，右儿子再入，左儿子最后

终止条件：栈空

前序遍历

vector<int>preorder(Node* root){
	stack<pair<TreeNode*, bool>> st;
        vector<int> res;
        if (root == NULL)
            return res;
        st.push(make_pair(root, false));
        while (!st.empty()) {
            TreeNode* now = st.top().first;
            bool flag = st.top().second;
            st.pop();
            if (flag) {
                res.push_back(now->val);
            } else {
                if (now->right != NULL) {
                    st.push(make_pair(now->right, false));
                }
                
                if (now->left != NULL) {
                    st.push(make_pair(now->left, false));
                }
                st.push(make_pair(now,true));
            }
        }
        return res;
}

中序遍历

vector<int>inorder(Node* root){
	stack<pair<TreeNode*, bool>> st;
        vector<int> res;
        if (root == NULL)
            return res;
        st.push(make_pair(root, false));
        while (!st.empty()) {
            TreeNode* now = st.top().first;
            bool flag = st.top().second;
            st.pop();
            if (flag) {
                res.push_back(now->val);
                
            } else {
                
                if (now->right != NULL) {
                    st.push(make_pair(now->right, false));
                }
                st.push(make_pair(now,true));
                if (now->left != NULL) {
                    st.push(make_pair(now->left, false));
                }
            }
        }
        return res;
    }

后序遍历

vector<int>backorder(Node* root){
	stack<pair<TreeNode*, bool>> st;
        vector<int> res;
        if (root == NULL)
            return res;
        st.push(make_pair(root, false));
        while (!st.empty()) {
            TreeNode* now = st.top().first;
            bool flag = st.top().second;
            st.pop();
            if (flag) {
                res.push_back(now->val);
                
            } else {
                st.push(make_pair(now,true));
                if (now->right != NULL) {
                    st.push(make_pair(now->right, false));
                }
                if (now->left != NULL) {
                    st.push(make_pair(now->left, false));
                }
            }
        }
        return res;
    }

迭代法：如果是前序和后序可以直接实现，如果是中序更适合使用统一迭代法

广度优先遍历法

层序遍历

用队列，每一层的顶点都放在队列里。

（1）每次弹出队首，记录在表示这一层的数组里，并且把队首的左儿子和右儿子记放进队列。

（2）把一层的节点都处理完之后保存这个表示层的数组。判断一层处理完的方法是：在处理这层之前记录一下这层元素个数，用for循环

（3）每一处理完一层之后，得到的队列里都是下一层的点

vector<vector<int>>levelorder(Node* root){
	vector<vector<int>>vec;
	queue<Node*> q;
	
	q.push(root);
	while(!q.empty()){
	vector<int>temp;
		int n=q.size();
		for(int i=0;i<n;i++){
			Node* now=q.front();
			q.pop();
			temp.push_back(now->val);
			if(now->left!=NULL)q.push(now->left);
			if(now->right!=NULL)q.push(now->right);
		}
		vec.push_back(temp);
	}
	return vec;
}

翻转二叉树

题干

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

思路

遍历，并翻转左右儿子即可

这里选择层序遍历

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL)
            return root;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* now = q.front();
            q.pop();
            TreeNode* temp = now->left;
            now->left = now->right;
            now->right = temp;
            if (now->left != NULL)
                q.push(now->left);
            if (now->right != NULL)
                q.push(now->right);
        }
        return root;
    }
};

对称二叉树

题干

给你一个二叉树的根节点 root ，检查它是否轴对称

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

思路

法一：层序遍历，每层判断是否对称

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> vec;
            for (int i = 0; i < n; i++) {
                TreeNode* now = q.front();
                if (now != NULL) {
                    vec.push_back(now->val);
                } else {
                    vec.push_back(-101);
                }
                q.pop();
                if (now != NULL)
                    q.push(now->left);
                if (now != NULL)
                    q.push(now->right);
            }
            res.push_back(vec);
        }
        for (int i = 0; i < res.size(); i++) {
            for (int j = 0; j < res[i].size() / 2; j++) {
                if (res[i][j] != res[i][res[i].size() - 1 - j]) {
                    return false;
                }
            }
        }
        return true;
    }
};

法二：递归遍历

对称要求外侧和外侧相等，内侧和内侧相等

从根节点的左右儿子来看，如果对称的话，左儿子和右儿子相等，左儿子的左儿子和右儿子的右儿子相等，且左儿子的左儿子和右儿子的右儿子相等

因此，每次判断两个点l和r的子树是否对称，

1）先看l和r是否相同

2）接下来先判断l->left和r->right，再判断l->right和r->left

class Solution {
public:
    bool match(TreeNode* left, TreeNode* right) {
        if (left == NULL && right == NULL)
            return true;
        else if (left == NULL && right != NULL)
            return false;
        else if (left != NULL && right == NULL)
            return false;
        else {
            if (left->val != right->val)
                return false;
            bool flag1 = match(left->left, right->right);
            bool flag2 = match(left->right, right->left);
            return flag1 && flag2;
        }
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL)
            return true;
        return match(root->left, root->right);
    }
};

前序求深度，后序求高度

最大深度

顶点深度是从根节点到该节点的路径长度，自顶向下计算。

顶点高度是从该节点到最远叶子节点的路径长度，自底向上计算。

树的高度是根节点的高度，表示整棵树的最大路径长度，也是树的最大深度

（1）层序遍历法

树的深度是根节点到叶子的最短路长度，最大深度用层数算

因此适合用层序遍历

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        queue<TreeNode*> q;
        q.push(root);

        int res = 0;
        while (!q.empty()) {
            int n = q.size();
            res++;
            for (int i = 0; i < n; i++) {
                TreeNode* now = q.front();
                q.pop();
                if (now->left != NULL)
                    q.push(now->left);
                if (now->right != NULL)
                    q.push(now->right);
            }
        }
        return res;
    }
};

（2）递归法：前序遍历和后序遍历均可

因为最大深度就是高度，深度用前序求，高度用后序求

now为根节点的子树的最大高度：

如果now为空，那么就是0

如果不是空，就是以右儿子为根的子树最大深度和以左儿子为根的子树最大深度的最大值，加1

最小深度

题干

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点

思路

递归

前序遍历和后序遍历都可以，这里使用后序。后序求的是是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离也同样是最小深度

以now为根节点的子树的最小深度：

如果左右儿子都是NULL，那么Now是叶子，最小深度为1

左儿子为NULL，右儿子不是，那么最小深度就是以右儿子为根的子树最小深度

左儿子不为NULL，右儿子为NULL，那么最小深度就是以左儿子为根的子树最小深度

左儿子和右儿子都不是NULL，那么最小深度就是以左儿子为根的子树最小深度和以右儿子为根的子树最小深度取最小值，再+1

class Solution {
public:
    int get_min(TreeNode* now) {
        if (now->left == NULL && now->right == NULL)
            return 1;
        else if (now->left != NULL && now->right == NULL)
            return get_min(now->left) + 1;
        else if (now->left == NULL && now->right != NULL)
            return get_min(now->right) + 1;
        else {
            int r = get_min(now->right);
            int l = get_min(now->left);
            return min(r, l) + 1;
        }
    }
    int minDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        return get_min(root);
    }
};

为什么不能在now为空的时候返回0：

[2,null,3,null,4,null,5,null,6]

3的左儿子是null ，如果null返回0，那么计算3的最小深度的时候，就会是min(0,右儿子最小深度)+1=1,但是3不是叶子，深度不是1

迭代：适合层序遍历

class Solution {
public:

    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;
    }
};

完全二叉树的节点个数

完全二叉树

除了最后一层外其他层全部填满的二叉树，最后一层的所有顶点都在左侧

（也就是倒数第二层的任何一个叶子都在内部顶点的右边，如果有出度为1的顶点，那么一定是有左儿子而没有右儿子

普通二叉树的做法

层序遍历

class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int h = 0;
        if (root == NULL)
            return 0;
        while (!q.empty()) {
            int n = q.size();

            for (int i = 0; i < n; i++) {
                TreeNode* now = q.front();
                q.pop();
                h++;
                if (now->left != NULL)
                    q.push(now->left);
                if (now->right != NULL)
                    q.push(now->right);
            }
        }
        return h;
    }
};

完全二叉树的做法

层遍历算出来有h层，1到h-1层有 $2^{h-1}$ 个节点，再加上最后一层的顶点数

class Solution {
public:
    int countNodes(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        q.push(root);
        int h = 0;
        if (root == NULL)
            return 0;
        while (!q.empty()) {
            int n = q.size();
            h++;
            vector<int> vec;
            for (int i = 0; i < n; i++) {
                TreeNode* now = q.front();
                q.pop();
                vec.push_back(now->val);
                if (now->left != NULL)
                    q.push(now->left);
                if (now->right != NULL)
                    q.push(now->right);
            }
            res.push_back(vec);
        }
        return pow(2, h - 1) - 1 + res[res.size() - 1].size();
    }
};

平衡二叉树

顶点深度是从根节点到该节点的路径长度，自顶向下计算。

顶点高度是从该节点到最远叶子节点的路径长度，自底向上计算。

树的高度是根节点的高度，表示整棵树的最大路径长度

递归

高度用后序求：先求左右儿子高度，再返回父亲高度

用-1表示不是平衡二叉树

求节点now的最大高度，如果Now为空，那么最大高度为0，分别求左右儿子的最大高度，差值大于1或有一个最大高度是-1，那么返回-1，其他的就是左右儿子的最大高度最大值+1

class Solution {
public:
    int get_h(TreeNode* now) {
        if (now == NULL)
            return 0;
        int left_h = get_h(now->left);
        int right_h = get_h(now->right);
        if (left_h == -1 || right_h == -1)
            return -1;
        if (abs(left_h - right_h) > 1)
            return -1;
        return max(left_h, right_h) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(get_h(root)==-1)return false;
        else return true;
        
    }
};

二叉树的所有路径

题干

给定一个二叉树，返回所有从根节点到叶子节点的路径

思路

选择遍历顺序：前序遍历，因为路径是从根部开始的

（1）2个栈 st实现统一形式的迭代法遍历，path存放已经找到的路径

（2）每次取出栈顶并弹出

1）没访问过，进行访问

2）访问过，进行处理

首先取path里的栈顶，弹出

如果st栈顶是叶子，加到结果数组

如果st栈顶不是叶子，将st栈顶的左右儿子加到路径上，路径加入path

注意：因为遍历顶点的顺序是前序（中左右），所以在处理路径的时候，也要先左后右，所以加入path的时候，先加右儿子的新路径

（3）计算路径是往当前节点的路径上加儿子的路径，这样是在root的基础上每次加->和新的点

vector<string> binaryTreePaths(TreeNode* root) {
        stack<pair<TreeNode*, bool>> st;
        stack<string> path;
        vector<string> res;
        st.push(make_pair(root, false));
        path.push(to_string(root->val));
        while (!st.empty()) {
            pair<TreeNode*, bool> now = st.top();
            st.pop();
            if (now.second == true) {
                string new_path = path.top();
                path.pop();
                if (now.first->left == NULL && now.first->right == NULL) {
                    res.push_back(new_path);
                } else if (now.first->left != NULL &&
                           now.first->right == NULL) {
                    path.push(new_path + "->" +
                              to_string(now.first->left->val));
                } else if (now.first->left == NULL &&
                           now.first->right != NULL) {
                    path.push(new_path + "->" +
                              to_string(now.first->right->val));
                } else {
                    path.push(new_path + "->" +
                              to_string(now.first->right->val));
                    path.push(new_path + "->" +
                              to_string(now.first->left->val));
                }
            } else {
                now.second = true;
                if (now.first->right != NULL)
                    st.push(make_pair(now.first->right, false));
                if (now.first->left != NULL)
                    st.push(make_pair(now.first->left, false));
                st.push(now);
            }
        }
        return res;
    }

左叶子之和

题干

给定二叉树的根节点 root ，返回所有左叶子之和

思路

前序遍历，迭代

如果当前点的左儿子是左叶子，就加起来

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL)
            return 0;
        stack<TreeNode*> st;
        int res = 0;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if (node->left != NULL) {
                if (node->left->left == NULL && node->left->right == NULL) {
                    res += node->left->val;
                } else {
                    st.push(node->left);
                }
            }
            if (node->right != NULL)
                st.push(node->right);
        }
        return res;
    }
};

找树左下角的值

题干

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

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

思路

层序遍历，取最后一层的第一个元素

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> res;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> vec;
            for (int i = 0; i < n; i++) {
                TreeNode* now = q.front();
                q.pop();
                vec.push_back(now->val);
                if (now->left != NULL)
                    q.push(now->left);
                if (now->right != NULL)
                    q.push(now->right);
            }
            res.push_back(vec);
        }
        return res[res.size() - 1][0];
    }
};

路径之和

题干

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

思路

前序遍历求路径

递归法

每次遇到一个顶点

（1）如果是空，那么就是根节点是空，返回false （这个只用来处理根节点是空的情况）

（2）不是空，就在targetSum当中减去当前节点的和

（3）如果当前节点是叶子，并且targetSum为0

（4）当前节点不是叶子，用flag1存放左子树是否有和为目标的路径，用flag2存放右子树是否有和为目标的路径，返回flag1||flag2

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL)
            return false;
        targetSum-=root->val;
        if (root->left == NULL && root->right == NULL && targetSum == 0)
            return true;
        bool flag1 = false;
        bool flag2 = false;
        if (root->left != NULL) {
            flag1 = hasPathSum(root->left, targetSum );
        }
        if (root->right != NULL) {
            flag2 = hasPathSum(root->right, targetSum );
        }
        return flag1 || flag2;
    }
};

完全包括递归和回溯的写法

1）先处理终止条件

2）单层递归

先处理左边，因为在count这个变量上进行加减，所以如果遍历到底发现不是符合条件的路径，就要恢复count

class Solution {
private:
    bool traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回

        if (cur->left) { // 左
            count -= cur->left->val; // 递归，处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯，撤销处理结果
        }
        if (cur->right) { // 右
            count -= cur->right->val; // 递归，处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯，撤销处理结果
        }
        return false;
    }

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

迭代法

前序遍历迭代求路径，用栈存放树的顶点，用栈存放路径长度

每次取出栈顶并弹出

（1）如果找到叶子并且路径和等于目标，那么返回true

（2）如果不是叶子

1）那么如果右儿子不为空，将右儿子放入顶点栈，原路径加右儿子放入路径栈

2）那么如果左儿子不为空，将左儿子放入顶点栈，原路径加左儿子放入路径栈

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) {
            return false;
        }
        stack<TreeNode*> tree;
        stack<int> path;
        tree.push(root);
        path.push(root->val);
        while (!tree.empty()) {
            TreeNode* now = tree.top();
            tree.pop();
            int path_now = path.top();
            path.pop();
            if (now->left == NULL && now->right == NULL) {
                if (path_now == targetSum)
                    return true;
            } else {

                if (now->right != NULL) {
                    tree.push(now->right);
                    path.push(path_now + now->right->val);
                }
                if (now->left != NULL) {
                    tree.push(now->left);
                    path.push(path_now + now->left->val);
                }
            }
        }
        return false;
    }
};

从中序和后序遍历构造二叉树

题干

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

思路

中序是左中右，不知道中在哪；后序是左右中，区分不了左右。因此从中序数组得到左右，在后续数组得到中

后序数组的末尾是当前的根（中），所以用后序数组的末尾分割中序数组，得到左子树和右子树。用这个结果在后序数组中区分左右子树

e.g inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

首先，从postorder得到，3是根，用3分割inorder，得到左右子树[9]和[15,20,7]，再分割postorder，得到左右子树[9]和[15,7,20]。分别看左右子树，左子树根为9，且为叶子；右子树根为20，分割中序，得到左右子树[15]和[17]

（1）递归终点：如果后序数组空了，就返回NULL

（2）寻找当前根节点：后序数组的最后一个元素

（3）分割中序数组：遍历中序数组，找到根节点的值存在的下标in_index

用下标得到中序数组左右子数组

[0,in_index-1] 左中序

[in_index+1,inorder.size()-1] 右中序

（4）分割后序数组

后序数组的前in_index-1和元素属于左子树，后免得元素去掉最后一个属于右子树

[0,in_index-1] 左后序

[in_index,inorder.size()-2] 右后序

（5）用左右子树的中序和后序数组得到左右儿子

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0)
            return NULL;
        TreeNode* root = new TreeNode(postorder[postorder.size() - 1]);
        int in_index;
        for (int i = 0; i < inorder.size(); i++) {
            if (inorder[i] == root->val)
                in_index = i;
        }
        vector<int> inorder_left(inorder.begin(), inorder.begin() + in_index);
        vector<int> inorder_right(inorder.begin() + in_index + 1,
                                  inorder.end());
        vector<int> postorder_left(postorder.begin(),
                                   postorder.begin() + in_index);
        vector<int> postorder_right(postorder.begin() + in_index,
                                    postorder.end() - 1);
        root->left = buildTree(inorder_left, postorder_left);
        root->right = buildTree(inorder_right, postorder_right);
        return root;
    }
};

构造最大二叉树

题干

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 nums 构建的 *最大二叉树* 。

思路

递归

每次找最大元素，构造当前顶点，作为子树根节点

如果数组里只剩下一个元素，直接返回当前节点

如果最大匀速左边，右边还有元素，用递归得到左右儿子

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode();
        if (nums.size() == 1) {
            node->val = nums[0];
            return node;
        }
        int max_value = -1;
        int max_index;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > max_value) {
                max_index = i;
                max_value = nums[i];
            }
        }
        node->val = max_value;
        if (max_index > 0) {
            vector<int> l(nums.begin(), nums.begin() + max_index);
            node->left = constructMaximumBinaryTree(l);
        } else {
            node->left = NULL;
        }
        if (max_index < nums.size() - 1) {
            vector<int> r(nums.begin() + max_index + 1, nums.end());
            node->right = constructMaximumBinaryTree(r);
        } else {
            node->right = NULL;
        }
        return node;
    }

合并二叉树

题干

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

思路

递归

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==NULL)return root2;
        if(root2==NULL)return root1;
        TreeNode* new_root=new TreeNode();
        new_root->val=root1->val+root2->val;
        new_root->left=mergeTrees(root1->left,root2->left);
        new_root->right=mergeTrees(root1->right,root2->right);
        return new_root;
        }
};

迭代

层序遍历

将root1 的树改造成合并后的树

每次处理，将队列最前的2个弹出（前面是root1 的，后面是root2的）
如果左儿子都不是空，那么给root1左儿子加上root2 左儿子
如果右儿子都不是空，那么给root1右儿子加上root2 右儿子
1的左儿子空，2 的左儿子不空：2 的左儿子幅值给1的左儿子
1的右儿子空，2 的右儿子不空：2 的右儿子幅值给1的右儿子

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空，val相加
            node1->val += node2->val;

            // 如果两棵树左节点都不为空，加入队列
            if (node1->left != NULL && node2->left != NULL) {
                que.push(node1->left);
                que.push(node2->left);
            }
            // 如果两棵树右节点都不为空，加入队列
            if (node1->right != NULL && node2->right != NULL) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 当t1的左节点 为空 t2左节点不为空，就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空，就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }
        }
        return t1;
    }
};

二叉搜索树的搜索

题干

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

思路

利用二叉搜索树的形式进行搜索

如果当前值大于val，向左边找；如果当前值小于val，向右边找

递归

TreeNode* searchBST(TreeNode* root, int val) {
        if (root==NULL)return NULL;
        
        if(root->val>val) return searchBST(root->left,val);
        if(root->val<val) return searchBST(root->right,val);
        return root;
    }

迭代

TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* p=root;
        while(p!=NULL){
            if(p->val>val) p=p->left;
            else if(p->val<val)p=p->right;
            else return p;
        }
    }

验证二叉搜索树

题干

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点数。
所有左子树和右子树自身必须也是二叉搜索树。

思路

（1）选择中序遍历：左中右的顺序遍历，如果前一个比后一个大，那么不是二叉搜索树

（2）不断地向左遍历，到最左边的叶子停下来，开始处理，因为最左边的元素理论上是最小的元素

（3）用pre记录当前元素root的前一个元素

pre是NULL：还没到最左边的顶点

pre不是NULL：已经到最左边了，正在进行比较大小

（4）对于left和right的递归在分别检验左右子树，中间对于“中”的处理，是检验当前节点是不是比前一个节点大。

（对左儿子的递归在不断向左走，找最左的顶点，对右的字的递归是沿着理论上的递增方向比较大小）

递归

class Solution {
public:
    TreeNode* pre = NULL;
    bool isValidBST(TreeNode* root) {
        if (root == NULL)
            return true;
        bool l = isValidBST(root->left);
        if (pre != NULL && pre->val >= root->val)
            return false;
        pre = root;
        bool r = isValidBST(root->right);
        return r && l;
    }
};

迭代

为什么比较当前是否大于前一个，而不是比较当前是否小于后一个：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<pair<TreeNode*, bool>> st;
        if (root == NULL)
            return true;
        st.push(make_pair(root, false));
        TreeNode* pre = NULL;
        while (!st.empty()) {
            pair<TreeNode*, bool> p = st.top();
            st.pop();
            if (p.second == false) {
                p.second = true;
                if (p.first->right != NULL)
                    st.push(make_pair(p.first->right, false));
                st.push(p);
                if (p.first->left != NULL)
                    st.push(make_pair(p.first->left, false));
            } else {

                if (pre != NULL && pre->val >= p.first->val)
                    return false;
                pre = p.first;
            }
        }
        return true;
    }
};

二叉搜索树的最小绝对差

题干

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

思路

（1）不可以只算父亲和左右儿子的差的绝对值（例如[236,104,701,null,227,null,911]这个输入，最小的绝对值差就不是父亲和儿子）

（2）中序遍历的时候，相当于一个升序数组，求前一个元素和后一个元素的差的绝对值，所以用pre记录前一个元素

递归

class Solution {
public:
    int res = 100001;
    // 中序遍历  左--中--右
    TreeNode* pre = NULL;
    void f(TreeNode* root) {
        if (root == NULL)
            return;
        f(root->left);
        if (pre) {
            int temp = abs(root->val - pre->val);
            res = min(res, temp);
        }
        pre = root;
        f(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        f(root);
        return res;
    }
};

迭代

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int res = 100001;
        stack<pair<TreeNode*, bool>> st;
        st.push(make_pair(root, false));
        TreeNode* pre = NULL;
        while (!st.empty()) {
            pair<TreeNode*, bool> p = st.top();
            st.pop();
            if (p.second) {
                if (pre) {
                    res = min(res, abs(pre->val - p.first->val));
                }
                pre = p.first;
            } else {
                if (p.first->right)
                    st.push(make_pair(p.first->right, false));
                p.second = true;
                st.push(p);
                if (p.first->left)
                    st.push(make_pair(p.first->left, false));
            }
        }
        return res;
    }
};

二叉搜索树求众数

题干

思路

如果不是二叉搜索树，怎么求众数：

用哈希表记录频率

class Solution {
public:
    bool static srt(pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> mp;
        stack<pair<TreeNode*, bool>> st;
        st.push(make_pair(root, false));
        while (!st.empty()) {
            pair<TreeNode*, bool> p = st.top();
            st.pop();
            if (p.second) {
                mp[p.first->val] += 1;
            } else {
                if (p.first->right)
                    st.push(make_pair(p.first->right, false));
                p.second = true;
                st.push(p);
                if (p.first->left)
                    st.push(make_pair(p.first->left, false));
            }
        }
        vector<pair<int, int>> vec(mp.begin(), mp.end());
        sort(vec.begin(), vec.end(), srt);
        vector<int> res;
        res.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            if (vec[i].second < vec[0].second)
                break;
            res.push_back(vec[i].first);
        }
        return res;
    }
};

利用二叉搜索树的性质

中序遍历得到有序数组，每次比较前一个和当前是否一样

（1）如果pre是NULL，说明当前节点是第一个，是当前众数，加入结果，count=1，maxcount=1

（2）中序遍历得到有序数组，每次比较前一个和当前是否一样

1）一样：count加一

2）不一样：count=1

（3）无论是否一样，都要进行：

1）如果count比maxcount大：清空结果数组，将当前加入结果，count=1

2）如果count比maxcount小：count=1

3）如果count等于maxcount：清空结果数组，将当前加入结果，count=1

注意：

1）为什么不能只在前一个和当前不一样的时候更新结果，并且将前一个作为结果（count记录前一个出现的次数：

因为存在最后一个节点是众数的情况，他和前一个相等，无法采集到

2）每一次求出count都更新，并且count是当前节点出现次数

class Solution {
public:
    TreeNode* pre = NULL;
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        stack<pair<TreeNode*, bool>> st;
        st.push(make_pair(root, false));
        int count;
        int max_count = 0;
        while (!st.empty()) {
            pair<TreeNode*, bool> p = st.top();
            st.pop();
            if (p.second) {
                if (pre == NULL) {
                    count = 1;
                    max_count = 1;
                    res.push_back(p.first->val);
                } else {
                    if (pre->val == p.first->val) {
                        count++;
                    } else {
                        count = 1;
                    }
                    if (count > max_count) {
                        max_count = count;
                        res.clear();
                        res.push_back(p.first->val);
                    } else if (count == max_count) {
                        res.push_back(p.first->val);
                    }
                }
                pre = p.first;
            } else {
                if (p.first->right)
                    st.push(make_pair(p.first->right, false));
                p.second = true;
                st.push(p);
                if (p.first->left)
                    st.push(make_pair(p.first->left, false));
            }
        }
        return res;
    }
};

二叉树的最近公共祖先

题干

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

找公共祖先，需要从下向上，也就是左右中的顺序

（1）如果当前节点是空，或者是P或q，就返回（函数本质上是找p和q）

（2）获取左子树中p和q的最小公共祖先（递归调用）记为l；获取右子树中p和q的最小公共祖先（递归调用）记为r

（3）如果l和r均不为空，说明p和q分别在两个子树里，当前节点为最小公共祖先（最小是因为从下到上），返回当前节点

（4）如果l空，r不为空，那么p和q都在右子树里，最小公共祖先就是r

（5）如果r空，l不为空，那么p和q都在左子树里，最小公共祖先就是l

（6）l和r都是空，那么p和q没被找到，返回NULL

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL || root==p || root==q)return root;
    
        TreeNode* l=lowestCommonAncestor(root->left,p,q);
        TreeNode* r=lowestCommonAncestor(root->right,p,q);
        if(l!=NULL && r==NULL)return l;
        if(r!=NULL && l==NULL)return r;
        if(r!=NULL && l!=NULL)return root;
        return NULL;

    }
};

二叉搜索树的公共祖先

题干

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

从上向下遍历，如果第一次遇到大小介于p和q之间的节点，p和q分别在这个节点的左右子树里，那么这个节点就是p和q的最近公共祖先

如果遇到的节点大于p和q，向左移动

如果遇到的节点小于p和q，向右移动

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL)
            return root;

        if (root->val > q->val && root->val > p->val) {
            return lowestCommonAncestor(root->left, p, q);
        }
        if (root->val < q->val && root->val < p->val)
            return lowestCommonAncestor(root->right, p, q);
        return root;
        // ((root->val>q->val&&root->val<p->val)||(root->val>p->val&&root->val<q->val))
    }
};

二叉搜索树的插入操作

题干

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 任意有效的结果 。

思路

把新的节点作为叶子更安全

（1）如果当前节点大于val：

1）左儿子为空：作为左儿子

2）左儿子不为空：向左移动

（2）如果当前节点小于val：

1）右儿子为空：作为右儿子

2）右儿子不为空：向右移动

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* add = new TreeNode();
        add->val = val;

        TreeNode* cur = root;
        while (cur) {
            if (cur->val > val) {
                if (cur->left) {
                    cur = cur->left;
                } else {
                    cur->left = add;
                    return root;
                }
            } else {
                if (cur->right) {
                    cur = cur->right;
                } else {
                    cur->right = add;
                    return root;
                }
            }
        }
        return add;
    }
};

删除二叉搜索树的节点

题干

思路

（1）先找值为key的点，并同时记录前一个点（cur的父亲）pre

（2）找到以后：

1）pre是空，说明要删除的点是root，那么在root上进行操作

<1>cur是叶子：root为空

<2>cur左儿子为空，右儿子不为空：root为右儿子

<3>cur左儿子不为空，右儿子为空：root为左儿子

<4>cur左右儿子都不为空

将cur的左子树移动到cur的右子树的最左边的叶子上当左儿子

再用cur的右儿子作为root

2）pre是空，要判断要删除的是pre的左儿子还是右儿子

如果pre的左儿子是cur

<1>cur是叶子：pre的左儿子为空

<2>cur左儿子为空，右儿子不为空：pre的左儿子为cur右儿子

<3>cur左儿子不为空，右儿子为空：pre的左儿子为cur的左儿子

<4>cur左右儿子都不为空

将cur的左子树移动到cur的右子树的最左边的叶子上当左儿子

再用cur的右儿子作为pre的左儿子

如果pre的右儿子是cur

<1>cur是叶子：pre的右儿子为空

<2>cur左儿子为空，右儿子不为空：pre的右儿子为cur右儿子

<3>cur左儿子不为空，右儿子为空：pre的右儿子为cur的左儿子

<4>cur左右儿子都不为空

将cur的左子树移动到cur的右子树的最左边的叶子上当左儿子

再用cur的右儿子作为pre的右儿子

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while (cur != NULL) {
            if (cur->val > key) {
                pre = cur;
                cur = cur->left;
            } else if (cur->val < key) {
                pre = cur;
                cur = cur->right;
            } else {
                if (pre == NULL) {
                    if (cur->left == NULL && cur->right == NULL)
                        return NULL;
                    else if (cur->left == NULL && cur->right != NULL) {
                        root = root->right;
                    } else if (cur->left != NULL && cur->right == NULL) {
                        root = root->left;
                    } else {
                        TreeNode* t = cur->right;
                        while (t->left) {
                            t = t->left;
                        }
                        t->left = cur->left;
                        root = cur->right;
                    }
                    return root;
                } else {
                    if (cur->left == NULL && cur->right == NULL) {
                        if (pre->left && pre->left->val == key)
                            pre->left = NULL;
                        else {
                            pre->right = NULL;
                        }
                    } else if (cur->left == NULL && cur->right != NULL) {
                        if (pre->left && pre->left->val == key)
                            pre->left = cur->right;
                        else {
                            pre->right = cur->right;
                        }
                    } else if (cur->left != NULL && cur->right == NULL) {
                        if (pre->left && pre->left->val == key)
                            pre->left = cur->left;
                        else {
                            pre->right = cur->left;
                        }
                    } else {
                        if (pre->left && pre->left->val == key) {
                            TreeNode* t = cur->right;
                            while (t->left) {
                                t = t->left;
                            }
                            t->left = cur->left;
                            pre->left = cur->right;
                        } else {
                            TreeNode* t = cur->right;
                            while (t->left) {
                                t = t->left;
                            }
                            t->left = cur->left;
                            pre->right = cur->right;
                        }
                    }
                    break;
                }
            }
        }
        return root;
    }
};

总结

1、遍历

2、获取路径：前序

3、求高度：后序

4、求深度：前序

5、构造二叉树：

已知中序和后序可以构造二叉树，已知前序和中序可以构造二叉树：

因为中序能分左右，但是找不到中；前序开头是中，后序结尾为中，都能找到中但是分不开左右

6、二叉搜索树

（1）二叉搜索树采用中序遍历，其实就是一个升序的有序数组

（2）验证二叉搜索树：不能只验证左儿子<父亲<右儿子，而是要中序遍历验证递增，需要设定一个指针pre记录前一个顶点

（3）二叉搜索树的搜索：不需要借助栈，当前大于目标就向左移动，小于目标向右移动

（3）对于二叉搜索树的操作，可以不先求数组，而是在树遍历过程中进行，需要记录前一个顶点的指针
}
} else if (cur->left == NULL && cur->right != NULL) {
if (pre->left && pre->left->val == key)
pre->left = cur->right;
else {
pre->right = cur->right;
}
} else if (cur->left != NULL && cur->right == NULL) {
if (pre->left && pre->left->val == key)
pre->left = cur->left;
else {
pre->right = cur->left;
}
} else {
if (pre->left && pre->left->val == key) {
TreeNode* t = cur->right;
while (t->left) {
t = t->left;
}
t->left = cur->left;
pre->left = cur->right;
} else {
TreeNode* t = cur->right;
while (t->left) {
t = t->left;
}
t->left = cur->left;
pre->right = cur->right;
}
}
break;
}
}
}
return root;
}
};




## 总结

### 1、遍历

### 2、获取路径：前序

### 3、求高度：后序

### 4、求深度：前序

### 5、构造二叉树：

已知中序和后序可以构造二叉树，已知前序和中序可以构造二叉树：

因为中序能分左右，但是找不到中；前序开头是中，后序结尾为中，都能找到中但是分不开左右

### 6、二叉搜索树

（1）==二叉搜索树采用中序遍历，其实就是一个升序的有序数组==

（2）验证二叉搜索树：不能只验证左儿子<父亲<右儿子，而是要中序遍历验证递增，需要设定一个指针pre记录前一个顶点

（3）二叉搜索树的搜索：不需要借助栈，当前大于目标就向左移动，小于目标向右移动

（3）对于二叉搜索树的操作，可以不先求数组，而是在树遍历过程中进行，需要记录前一个顶点的指针

查看全文

http://www.kler.cn/a/531785.html