LeetCode贪心算法章节

LeetCode二叉树章节

二叉树的递归遍历

形式固定，相对简单，不同遍历仅仅改变代码顺序

  • 先序递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//中左右
//            1
//         /     \
//        2       3
//       /  \    /  \
//      4    5  6    7     遍历顺序 1 - 2 - 4 - 5 - 3 - 6 - 7

struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;

TreeNode():val(0),left(nullptr),right(nullptr){}
TreeNode(int x):val(x),left(nullprt),right(nullptr){}
TreeNode(int x,TreeNode* leftnode, TreeNode* rightnode):val(x),left(leftnode),right(rightnode){}
};

class Solution{
public:
	vector<int> res;
    vector<int> preorder(TreeNode* root)//用数组返回储存遍历的结点的值
    {
        if(!root) return res;
        res.push_back(root->val);	//中
        preorder(root->left);	 	//左
        preorder(root->right);	 	//右
        return res;
    }
};
  • 中序递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//左中右
//            1
//         /     \
//        2       3
//       /  \    /  \
//      4    5  6    7     遍历顺序 4 - 2 - 5 - 1 - 6 - 3 - 7

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:
    vector<int> res;
    vector<int> inorder(TreeNode* root)
    {
        if(!root) return res;
        inorder(root->left);          //左
        res.push_back(root->val);	  //中
        inorder(root->right);		 //右
        return res;
    }
};
  • 后序递归遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    //左右中
    //            1
    //         /     \
    //        2       3
    //       /  \    /  \
    //      4    5  6    7     遍历顺序 4 - 5 - 2 - 6 - 7 - 3 - 1

    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:
        vector<int> res;
        vector<int> postorder(TreeNode* root)
        {
            if(!root) return res;
            postorder(root->left);		//左
            postorder(root->right);		//右
            res.push_back(root->val);	//中
            return res;
        }
    };

二叉树的迭代遍历

先、中、后序遍历均属于DFS（深度优先搜索算法），借助栈实现

而层序遍历为BFS（广度优先搜索算法），借助队列实现

  • 先序迭代遍历

对于先序迭代遍历（中左右）和后序迭代遍历（左右中），访问顺序和处理顺序相同，仅需要改变入栈顺序，再翻转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//中左右
//            1
//         /     \
//        2       3
//       /  \    /  \
//      4    5  6    7     遍历顺序 1 - 2 - 4 - 5 - 3 - 6 - 7

struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;

TreeNode():val(0),left(nullptr),right(nullptr){}
TreeNode(int x):val(x),left(nullprt),right(nullptr){}
TreeNode(int x,TreeNode* leftnode, TreeNode* rightnode):val(x),left(leftnode),right(rightnode){}
};

class Solution{
public:
	vector<int> res;
    vector<int> preorder(TreeNode* root)//用数组返回储存遍历的结点的值
    {
        if(!root) return res;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty())
        {
        	TreeNode* node = stk.top();
        	stk.pop();
        	res.push_back(node->val);				//中
        	if(node->right) stk.push(node->right);	 //右，保证空结点不入栈
        	if(node->left) stk.push(node->left);	 //左，保证空结点不入栈
        	//由于栈的先进后出，后进先出的特性，先将右节点入栈，再将左节点入栈
        }
        return res;
    }
};
  • 后序迭代遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    //左右中
    //            1
    //         /     \
    //        2       3
    //       /  \    /  \
    //      4    5  6    7     遍历顺序 4 - 5 - 2 - 6 - 7 - 3 - 1

    struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int x):val(x),left(nullprt),right(nullptr){}
    TreeNode(int x,TreeNode* leftnode, TreeNode* rightnode):val(x),left(leftnode),right(rightnode){}
    };

    class Solution{
    public:
    	vector<int> res;
        vector<int> preorder(TreeNode* root)//用数组返回储存遍历的结点的值
        {
            if(!root) return res;
            stack<TreeNode*> stk;
            stk.push(root);
            while(!stk.empty())
            {
            	TreeNode* node = stk.top();
            	stk.pop();
            	res.push_back(node->val);				//中
            	if(node->left) stk.push(node->left);	 //左，保证空结点不入栈
            	if(node->right) stk.push(node->right);	 //右，保证空结点不入栈
            	//由于栈的先进后出，后进先出的特性，先将左节点入栈，再将右节点入栈，翻转后符合左右中
            }
            return reverse(res.begin(),res.end());
        }
    };
  • 中序迭代遍历

而中序迭代遍历（左中右）先访问中间结点，但先处理左结点（存入数组），故需要额外用cur指针不断指向最左结点并将沿路左结点入栈，先处理左结点随后不断回退读取中间结点和右结点完成遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//左中右
//            1
//         /     \
//        2       3
//       /  \    /  \
//      4    5  6    7     遍历顺序 4 - 2 - 5 - 1 - 6 - 3 - 7

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:
    vector<int> res;
    vector<int> inorder(TreeNode* root)
    {
        if(!root) return res;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        while(!stk.empty()||!cur)
        {
        	if(!cur) 				//cur已指向最左结点的左结点(nullptr)
        	{
        		TreeNode* node = stk.top();
                 stk.pop();
                 res.push_back(node->val);					//中
                 
                 
                 
                 if(node->right) stk.push(node->right);		 //右      有漏洞
                 
                 
                 
        	}
        	else					//cur不指向空结点时
        	{
        		stk.push(cur);							   //左，且保证空结点不入栈
                 cur = cur->left;
        	}
        }
        return res;
    }
};

上述代码段有漏洞，原因在于 if(node->right) stk.push(node->right) ，没有考虑到当前右结点还有左结点的可能性，从而导致没有完全遍历。因此，并不需要创建新节点 TreeNode* node ，而是继续赋值给cur指针

1
2
3
4
5
6
if(!cur)
{
    cur = stk.top();
    stk.pop();
    cur = cur->right;
}

继续让cur 指针指向子树中的最左结点，完成遍历。

  • 层序迭代遍历
    因为需要边访问（入）边处理结点（出），栈无法满足使用需求，因此使用队列完成层序迭代遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    //            1
    //         /     \
    //        2       3
    //       /  \    /  \
    //      4    5  6    7     遍历顺序 1 - 2 - 3 - 4 - 5 - 6 - 7

    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:
    	vector<int> res;
    	vector<int> levelorder(TreeNode* root)
    	{
    		if(!root) return res;
    		queue<TreeNode*> que;
    		que.push(root);
    		while(!que.empty())
    		{
    			int qsize = que.size();
    			for(int i = 0; i<qsize;i++)
    			{
                    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;
    	}
    };

翻转二叉树

[LeetCode226](226. 翻转二叉树 - 力扣（LeetCode）)

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

示例1：

示例1

aa

示例2：

示例2

递归法

首先，可以考虑递归，并使用swap(TreeNode* left,TreeNode* right)函数完成左右子结点的交换，即翻转。考虑到处理顺序，可以使用先序递归遍历。

  1. 确定递归的终止条件
    1
    if(!root) return root;
    ①不判断root->left或root->right是否为空，会导致也将叶子结点也进行翻转，造成一定的浪费；②或递归前判断是否空结点，空结点不进入到下一层递归；③或考虑root->left或root->right是否为空，减少对叶子结点翻转的时间开销。
  2. 确定递归的返回值
    由题目要求返回翻转后的根节点可知返回root结点
    1
    2
    TreeNode* invertTree(TreeNode* root)
    return root;
  3. 单层递归中的逻辑处理
    1
    2
    3
    swap(root->left,root->right);
    if(root->let) invertTree(root->left);
    if(root->right) invertTree(root->right);
    整体代码如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    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){}
    };

    //全部非空结点都对其子结点进行翻转，多耗费O(2^(h-1))的时间，h为二叉树层高
    //①
    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if(!root) return root;
            swap(root->left,root->right);
    	    if(root->left) invertTree(root->left);
    	    if(root->right) invertTree(root->right);
            return root;
        }
    };

    //对子结点进行判断，非子结点才进行递归，子结点不进入递归
    //②
    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if(!root) return root;
            if(!root->left&&!root->right) return root;  //子结点则退出递归
            if(root->left&&(root->left->left||root->left->right)) invertTree(root->left);//判断是否子结点
            if(root->right&&(root->right->left||root->right->right)) invertTree(root->right);
            swap(root->left,root->right);
            return root;
        }
    };

    //如果是子结点则退出递归，非子结点和子结点都进入递归
    //③
    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if(!root) return root;
            if(!root->left&&!root->right) return root;
            swap(root->left,root->right);
    	    if(root->left) invertTree(root->left);
    	    if(root->right) invertTree(root->right);
            return root;
        }
    };

在对结点的子结点的子结点进行判断时，要注意结点的子结点的空指针判断！

if(root->left->left||root->left->right)则忽略掉了root->left是空结点的可能性，

应改为if(root->left&&(root->left->left||root->left->right))

迭代法

下面是迭代的解法

很容易想到层序迭代遍历，对每个结点进行遍历然后对其子结点进行翻转；亦或者用先序迭代遍历和后序迭代遍历，都能达到翻转整棵二叉树的效果。唯独不能使用中序迭代遍历，因为左中右的处理顺序，在处理中间结点时，会将原来的左右子树也翻转，这就导致按照左中右来翻转二叉树，实际上是左中左的翻转操作顺序。

迭代解法不再考虑子结点是否为空，统一只判断当前结点是否为空，即也对叶子结点进行翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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) return root;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
        	int qsize = que.size();
        	for(int i = 0; i<qsize;i++)
        	{
        		TreeNode* node = que.front();
        		que.pop();
        		swap(node->left,node->right);
        		if(node->left) que.push(node->left);
        		if(node->right) que.push(node->right);
        	}
        }
        return root;
    }
};

//先序迭代遍历
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty())
        {
        	TreeNode* node = stk.top();
        	stk.pop();
        	swap(node->left,node->right);				//中
        	if(node->right) stk.push(node->right);		//右
        	if(node->left) stk.push(node->left);		//左
        	//swap(node->left,node->right);				//中，后序遍历
        }
        return root;
    }
};

总结

翻转二叉树题目中，主要需要注意到对结束条件的判断以及后续要处理结点的条件约束，如是否需要处理叶子结点。如果设定要非叶子结点才能进入判断即!root->left->left||!root->left->right，需要先加入判断root->left!=nullptr保证孙子结点能够被合法访问

对称二叉树

[对称二叉树](Loading Question… - 力扣（LeetCode）)

检查以root为根节点的树是否对称

递归法

首先，可以想到递归法，递归函数传入两个结点，判断其值是否相等，并把下一个要判断的结点放入递归栈中

  1. 判断递归结束条件
    1
    2
    3
    4
    if(!root) return true;

    if(left==nullptr&&right==nullptr) return true;
    if(left->val!=right->val) return false;
  2. 递归返回值
    1
    2
    bool judge(TreeNode* left,TreeNode* right)
    return true;
  3. 单层递归函数
    1
    2
    3
    4
    5
    6
    if(left->val==right->val)
    {
        judge(left->left,right->right);
        judge(right->left,left->right);
    }

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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:
	bool judge(TreeNode* left,TreeNode* right)
	{
		if(left==nullptr&&right==nullptr)	return true;
		if(left==nullptr&&right!=nullptr)	return false;
		if(left!=nullptr&&right==nullptr)	return false;
        bool flagleft,flagright;
		if(left->val!=right->val)	return false;
		else
		{
			flagleft = judge(left->left,right->right);
			flagright = judge(left->right,right->left);
		}
        return flagleft&&flagright;
	}
    bool isSymmetric(TreeNode* root) {
        if(!root)   return true;
        bool flag = judge(root->left,root->right);
        return flag;
    }
};

迭代法

选择层序迭代遍历最为恰当

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode():val(0),left(nullptr),right(nullptr){}
	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
};

//层序迭代遍历
class Solution{
public:
	bool isSymmetric(TreeNode* root)
    {
        if(!root) return true;
        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);
        while(!que.empty())
        {
            TreeNode* left = que.front();
            que.pop();
            TreeNode* right = que.front();
            que.pop();
            if(left==nullptr&&right==nullptr)	continue;
            else if(left==nullptr&&right!=nullptr)	return false;
            else if(left!=nullptr&&right==nullptr)	return false;
            else if(left->val!=right->val)	return false;
            que.push(left->left);
            que.push(right->right);
            que.push(left->right);
            que.push(right->left);
        }
        return true;
    }
};

总结

这道题主要要对不同情况进行分类判断，并且要注意后续进行两两判断的结点，递归法更为清晰；迭代法则需要注意当left==nullptr&&right==nullptr时并不能直接返回true与递归法不同，因为递归法返回的是上一层递归，仍需要继续对其他结点进行判断，因此在使用迭代法时需要对返回值特别注重，另外，在迭代法中不能强行按照模板for(int i = 0;i<que.size();i++，在本题中，由于每次处理所读取的队头元素并不只有一个，因为不能用队列数量来给定处理结点的次数。

二叉树最大深度

[二叉树最大深度](Loading Question… - 力扣（LeetCode）)

对于求最大深度，可以首先想到层序迭代遍历，用level来记录深度，每执行一轮就level++，最后返回level输出答案。层序迭代遍历时间复杂度为O(n)，n为结点数，空间复杂度最大为O(n)

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode():val(0),left(nullptr),right(nullptr){}
	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
};

class Solution{
public:
	int maxDepth(TreeNode* root)
	{
		if(!root) return 0;
		int level = 0;
		queue<TreeNode*> que;
		que.push(root);
		while(!que.empty())
		{
			int qsize = que.size();
			for(int i =0;i<qsize;i++)
			{
				TreeNode* node = que.front();
				que.pop();
				if(node->left) que.push(node->left);
				if(node->right)	que.push(node->right);
			}
			level++;
		}
		return level;
	}
};

递归法

先序递归遍历

  1. 确定递归终止判断条件
    1
    if(!root->left&&!root->right)	return level;
  2. 确定返回值
    1
    2
    3
    private: int level = 0;
    int maxDepth(TreeNode* root)
    return level;
  3. 确定单层递归函数
    1
    2
    3
    4
    void dfs(TreeNode* node,int level)
    level++;				//中
    dfs(root->left,level);	 //左
    dfs(root->right,level);	 //右

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode():val(0),left(nullptr),right(nullptr){}
	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
};

class Solution{
public:
int res = 0;
	void dfs(TreeNode* node, int level)
	{
		if(!node) return;
		res = max(level,res);			//中
		dfs(node->left,level+1);		//左
		dfs(node->right,level+1);		//右
	}
	int maxDepth(TreeNode* root)
	{
		if(!root) return 0;
		dfs(root,1);
		return res;
	}
};

后序递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode():val(0),left(nullptr),right(nullptr){}
	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
};

class Solution{
public:
int res = 0;
	int dfs(TreeNode* node)
	{
		if(!node) return 0;
		int llevel = dfs(node->left);
		int rlevel = dfs(node->right);
		return max(llevel,rlevel)+1;
	}
	int maxDepth(TreeNode* root)
	{
		if(!root) return 0;
		res = dfs(root);
		return res;
	}
};

递归法时间复杂度O(n)，空间复杂度为O(h)，h为树高

总结

层序遍历迭代法更容易理解，但付出空间复杂度可能更高的代价；递归法有先序递归遍历和后序递归遍历，先序递归遍历是由顶至底的遍历顺序，求的是从根节点开始的二叉树深度，而后序递归遍历则是由底至顶的遍历顺序，求的是从叶子结点开始的二叉树高度。也正因如此，先序递归遍历首先处理中间结点，level++，不需要返回值；而后序递归遍历最后处理中间结点，在此之前已得出子结点的高度，则需要返回值并加一，表示返回当前的高度。

N叉树最大深度

递归法

后序递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution{
public:
	int dfs(Node* node)
	{
		int res = 0;
		if(!node) return 0;
		for(Node* child : node->children)
		{
			int clevel = dfs(child);
			res = max(res,clevel);
		}
		return res+1;
	}
	int maxDepth(Node* root)
	{
		if(!root) return 0;
		int res = dfs(root);
		return res;
	}
};

先序递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution{
public:
int res = 0;
	void dfs(Node* node,int level)
	{
		if(!node) return;
		res = max(res,level);
		for(Node* child : node->children)
			dfs(child,level+1);
	}
	int maxDepth(Node* root)
	{
		if(!root) return 0;
		dfs(root,1);
		return res;
	}
};

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution{
public:
	int maxDepth(Node* root)
	{
		if(!root) return 0;
		int level = 0;
		queue<Node*> que;
		que.push(root);
		while(!que.empty())
		{
			int qsize = que.size();
			for(int i =0;i<qsize;i++)
			{
				Node* node = que.front();
				que.pop();
				for(Node* child:node->children)
					que.push(child);
			}
			level++;
		}
		return level;
	}
};

总结

与二叉树最大深度如出一辙。注意如何获取children结点，

vector<Node *> children = root->children;

for(auto child:children)

二叉树最小深度

[二叉树最小深度](111. 二叉树的最小深度 - 力扣（LeetCode）)

递归法

先序递归遍历

  1. 确定递归结束条件

    1
    2
    3
    4
    5
    if(!root->left&&root->right)
    {
    	res = min(res,level);
    	return;
    }

  2. 确定返回值

1
2
void dfs(TreeNode* root, int level)
return;

  1. 确定单层递归逻辑

    1
    2
    dfs(root->left,level+1);
    dfs(root->right,level+1);

整体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode():val(0),left(nullptr),right(nullptr){}
	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
};

class Solution{
public:
int res = INT_MAX;
	void dfs(TreeNode* node, int level)
	{
		if(!node->left&&!node->right)
        {
        	res = min(res,level);						//中
        	return;
        }
		if(node->left)	dfs(node->left,level+1);		//左
		if(node->right)	dfs(node->right,level+1);		//右
	}
	int minDepth(TreeNode* root)
	{
		if(!root) return 0;
		dfs(root,1);
		return res;
	}
};

同理，后序遍历做法模仿二叉树最大深度，整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode():val(0),left(nullptr),right(nullptr){}
	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
};

class Solution{
public:
	int dfs(TreeNode* node)
	{
		if(!node->left&&!node->right)
        	return 0;
        int llevel = INT_MAX,rlevel = INT_MAX;
        if(node->left)
		    llevel = dfs(node->left);		//左
		if(node->right)
            rlevel = dfs(node->right);		 //右
		return min(llevel,rlevel) + 1;
	}
	int minDepth(TreeNode* root)
	{
		if(!root) return 0;
		return dfs(root) + 1;
	}
};

另一种后序递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode():val(0),left(nullptr),right(nullptr){}
	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
};

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + getDepth(node->right);
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + getDepth(node->left);
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

    int minDepth(TreeNode* root) {
    	if(!root)	return 0;
        return getDepth(root);
    }
};

迭代法

层序迭代遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode():val(0),left(nullptr),right(nullptr){}
	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
};

class Solution{
public:
	int minDepth(TreeNode* root)
	{
		if(!root) return 0;
		int res =INT_MAX;
		int level = 1;
		queue<TreeNode*> que;
		que.push(root);
		while(!que.empty())
		{
			int qsize = que.size();
			for(int i = 0; i < qsize; i++)
			{
				TreeNode* node = que.front();
				que.pop();
				if(!node->left&&!node->right)//只有到达叶子结点才更新res
				{
					res = min(res,level);
				}
				if(node->left)	que.push(node->left);
				if(node->right)	que.push(node->right);
			}
			level++;
		}
		return res;
	}
};

总结

这题的突破点主要在于理解只有在到达叶子结点时才是二叉树的深度，即[2,null,3,null,4,null,5,null,6]的最小深度不是1，而是5。另外，在递归遍历中，可以根据不同的递归判断（判断是否让该结点进入下一层递归），来确定不同的返回值，如if(!node) return 0;或if(!node->left&&!node->right)，并且如果是后者，需要先判断node结点本身是否为空，否则会报错；如果是前者，则必须保证能够让单亲结点进入递归（否则直接返回错误的最小深度）

完全二叉树的结点个数

[完全二叉树的结点个数](222. 完全二叉树的节点个数 - 力扣（LeetCode）)

最直观的做法就是遍历每个结点，非空则计数+1，直至遇到空结点，可采用先序、中序和后序的递归遍历、迭代遍历法，也可以用层序迭代遍历法

递归法

先序递归遍历

  1. 确定递归结束条件
    1
    if(!node) return;
  2. 确定返回值
    1
    2
    3
    int sum = 0;
    void dfs(TreeNode* node)
    return;
  3. 确定单层逻辑
    1
    2
    3
    sum++;
    dfs(node->left);
    dfs(node->right);
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    struct TreeNode{
    	int val;
    	TreeNode* left;
    	TreeNode* right;
    	
    	TreeNode():val(0),left(nullptr),right(nullptr){}
    	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
    	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
    };

    class Solution {
    public:
        int sums = 0;
        void dfs(TreeNode* node)
        {
        	if(!node)	return;
        	sums++;
        	dfs(node->left);
        	dfs(node->right);
        }
        int countNodes(TreeNode* root) {
        	if(!root)	return 0;
        	dfs(root);
            return sums;
        }
    };

迭代法

中序迭代遍历法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode():val(0),left(nullptr),right(nullptr){}
	TreeNode(int val):val(val),left(nullprt),right(nullprt){}
	TreeNode(int val,TreeNode*left,TreeNode*right):val(val),left(left),right(right){}
};

class Solution {
public:
    int countNodes(TreeNode* root) {
    	if(!root)	return 0;
        //中序迭代遍历
        int res = 0;
    	stack<TreeNode*> stk;
        TreeNode* cur = root;

        while(cur!=nullptr||!stk.empty())
        {
            if(!cur)
            {
                cur = stk.top();stk.pop();
                res++;
                cur = cur->right;
            }
            else
            {
                stk.push(cur);
                cur = cur->left;
            }
        }
        return res;
    }
};

special解法

然而，以上方法都只是遍历所有结点才能确定结点个数，只是单纯当成一个普通的二叉树，时间复杂度都是O(n)。可以利用完全二叉树的性质来减小时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*对于一颗完全二叉树，如果找到最底层是n，可以用公式计算前n-1层的结点数`2^(n-1)-1`再加上第n层的结点

对于第n层上的结点，利用二分法不断缩小范围来找到最后一个结点

			  1
		   /      \
		  2        3
		 / \      / \
		4   5    6   7

给定二分法的范围，通过序号的二进制数顺序即可判断结点是否存在，如在level = 3，序号为6的结点，二进制数为110，取除最高位剩下的即10,从根节点出发，1代表右子树，0代表左子树，则根节点的右子树的左子树即为该节点;再如level = 4，序号为9的结点，除最高位剩下的二进制数为001，即代表从根节点出发，其左子树的左子树的右子树即为该结点
*/

class Solution {
public:
	bool is_exist(TreeNode* root, int level, int index)
	{
		int cmp = 1<<(level - 2);
		//cmp 用作取序号index对应位置上的数
        TreeNode* node = root;
		while(node!=nullptr&&cmp)
		{
			if(cmp&index)
				node = node->right;
			else
				node = node->left;
			cmp >>= 1;
		}
		return node!=nullptr;
	}
    int countNodes(TreeNode* root) {
    	if(!root)	return 0;
    	//先循环左子树找出树高
    	int level = 1;
    	TreeNode* node = root;
    	while(node->left)
    	{
    		level++;
    		node = node->left;
    	}
    	//这时node结点为二叉树最大深度的最左结点
    	int left = 1 << (level - 1), right = (1 << level) - 1;
    	//left 指向最大深度的最左结点，right 指向最大深度的最右结点
    	while(left < right)
    	{
    		int mid = left + (right - left + 1) / 2;	//+1为了防止死循环
    		if(is_exist(root,level,mid))
    			left = mid;
    		else
    			right = mid -1;
    	}
    	//此时，mid即为最大结点序号
     	return left;
    }
};

对于上述程序的时间复杂度，循环查找二叉树最大深度O(logn)，二分法时间复杂度O(logn)，但嵌套了时间复杂度为O(log n)的结点存在判断算法，因此总的时间复杂度为O(log n+log n^2)`

时间复杂度：O(log^2 n)，其中 n 是完全二叉树的节点数。

首先需要 O(h)的时间得到完全二叉树的最大层数，其中 h 是完全二叉树的最大层数；使用二分查找确定节点个数时，需要查找的次数为 O(log2^h)=O(h)，每次查找需要遍历从根节点开始的一条长度为 h 的路径，需要 O(h)的时间，因此二分查找的总时间复杂度是 O(h^2)。因此总时间复杂度是 O(h^2)，由于完全二叉树满足 2^h <= n <=2^(h+1)，因此有 O(h)=O(log n)，O(h^2)=O(\log^2 n)

总结

在题目中的位运算解法中，需要弄清楚完全二叉树的特殊性质，即结点按顺序从左到右依次填满，以及可以通过序号反推从根节点开始到该结点的路径，并且清楚位运算中1 << n等价于1*2^n，在运算时间上位运算也会更有优势，再结合二分法即可在小于O(n)的时间复杂度内完成

平衡二叉树

[平衡二叉树](110. 平衡二叉树 - 力扣（LeetCode）)

由顶至底法

最容易想到的一种方法就是分别求出左右子树的高度，再根据两者的差值进行判断。若是用先序遍历（求树深）的方法来做，需要有更多变量来保存临时树深和最大树深，因此更适合用后序遍历来做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
	int dfs(TreeNode* node)
	{
		if(!node)	return 0;
        int llevel = dfs(node->left);
        int rlevel = dfs(node->right);
		return max(llevel,rlevel)+1;
	}
    bool isBalanced(TreeNode* root) {
		if(!root)	return true;
        if(abs(dfs(root->right)-dfs(root->left))>1)
            return false;
		return true;
    }
};

上述方法还有个bug，没有考虑到子树本身是否平衡，因此需要再对子树进行平衡判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
	int dfs(TreeNode* node)
	{
		if(!node)	return 0;
         int llevel = dfs(node->left);
         int rlevel = dfs(node->right);
		return max(llevel,rlevel)+1;
	}
    bool isBalanced(TreeNode* root) {
		if(!root)	return true;
         if(abs(dfs(root->right)-dfs(root->left))>1)
            return false;
		return isBalanced(root->left)&&isBalanced(root->right);
    }
};

由于进行了大量的重复运算，最坏情况下时间复杂度为O(n^2)

由底至顶法

上述代码中，重复运算的原因在于子树高度时一旦遇到子树的子树不平衡时，没有及时向上返回，而是只返回最大深度，这就导致了还要对子树的子树进行额外的重复运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int dfs(TreeNode* node)
    {
        if (!node)	return 0;
        int llevel = dfs(node->left);
        if (llevel == -1)	return -1;
        int rlevel = dfs(node->right);
        if (rlevel == -1)	return -1;
        return abs(llevel - rlevel) > 1 ? -1 : max(llevel, rlevel) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if (!root)	return true;
        return dfs(root) != -1;
    }
};

时间复杂度为O(n)，最多每个结点运算一次

总结

进一步理解求树深用先序遍历，求树高用后序遍历。在做判断二叉树是否符合某种要求题目时，不仅要考虑根节点，还要考虑其子树是否同样符合。

由底至顶法提到，涉及到判断树是否符合某种条件时，一旦遇到不符合的，应立即向上返回，避免做其他开销，只需要加多判断语句，在本题中，形象上看起来就像是由底至顶地判断

二叉树的所有路径

[二叉树的所有路径](257. 二叉树的所有路径 - 力扣（LeetCode）)

递归法

  1. 递归结束条件

    1
    if(!node->left&&!node->right)

  2. 递归返回值

    ​ 递归结束时即遇到了叶子结点，则证明改路径结束，应该返回整条路径并输出到res中

    1
    2
    3
    4
    5
    void traversal(TreeNode* node)
    {
    	//将path整条打印成"node1->node2->...->noden"格式
    	return;
    }

  3. 单层递归逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    if(node->left) 
    {
    	traversal(node->left);
    	path.pop_back();//回溯
    }
    	
    if(node->right)
    {
    	traversal(node->right);
    	path.pop_back();
    }

整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    void traversal(TreeNode* node, vector<string> &res, vector<TreeNode*> &path)
    {
        path.push_back(node);
        if (!node->left&&!node->right)//叶子结点则路径结束
        {
            string str;
            for (int i = 0; i < path.size() - 1; i++)
            {
                str += to_string(path[i]->val);
                str += "->";
            }
            str += to_string(path.back()->val);
            res.push_back(str);
            path.pop_back();
            return;
        }
        
        if(node->left)  traversal(node->left, res, path);
        if(node->right) traversal(node->right, res, path);
        path.pop_back();

    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        vector<TreeNode*>path;
        traversal(root, res, path);
        return res;
    }
};

总结

本题是第一次遇到回溯算法，在二叉树中的回溯算法结合递归可能较难以理解，需要多加模拟回溯过程，体验不同的回溯方式可以更好理解。因为要求按顺序打印路径，此题就需要用先序遍历（先打印的是根结点），但一般来说，回溯法使用后序遍历更简便

左叶子之和

[左叶子之和](404. 左叶子之和 - 力扣（LeetCode）)

首先要清楚如何判断是否是左叶子结点，哪种情况下才能算是左叶子，例如[1,null,2]中并不存在左叶子。因此可以得到关键判断语句if(root->left&&!root->left->left&&!root->left->right)，这是解题的关键

递归法

后序递归遍历

  1. 确定递归结束条件

    遇到左叶子或者遇到叶子结点即返回

    1
    if(root->left&&!root->left->left&&!root->left->right) return lsum+rsum+root->left->val;

  2. 确定递归返回值

    1
    2
    3
    int dfs(TreeNode* node)
    int lsum = 0,rsum = 0;
    return lsum + rsum;

  3. 单层递归逻辑

    1
    2
    if(node->left)	dfs(root->left);
    if(node->right)	dfs(root->right);

整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int dfs(TreeNode* node)
    {
        int lsum = 0,rsum = 0;
        if (node->left) 
            lsum = sumOfLeftLeaves(node->left);
        if (node->right) 
            rsum = sumOfLeftLeaves(node->right);
        if (node->left && !node->left->left && !node->left->right)//左叶子结点
            return node->left->val+lsum+rsum;
        return lsum + rsum;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root->left && !root->right) return 0;
        return dfs(root);
    }
};

因为在进入递归之前加上了结点是否为空的判断，因此在递归结束判断条件中并不是传统的if(!node)判断，只需要判断是否为左叶子即可

先序递归遍历

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int res = 0;
    void dfs(TreeNode* node)
    {
        if (node->left && !node->left->left && !node->left->right)//左叶子结点
            res += node->left->val;
        if (node->left) sumOfLeftLeaves(node->left);
        if (node->right) sumOfLeftLeaves(node->right);
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root->left && !root->right) return 0;
        dfs(root);
        return res;
    }
};

先序递归遍历代码只是对左叶子的判断语句提前，符合先序遍历中左右的结点处理顺序

迭代法

迭代法采用层序迭代遍历，代码思路较为简单直接

整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==nullptr)   
            return 0;
        int res = 0;
        queue<TreeNode*> que;
        TreeNode* node;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            for(int i = 0;i<size;i++)
                {
                    node = que.front();
                    que.pop();
                    if(node->left)
                    {
                        que.push(node->left);
                        if(node->left->left == nullptr&&node->left->right ==nullptr)
                            res+=node->left->val;
                    }
                    if(node->right)
                        que.push(node->right);
                }
        }
        return res;
    }
};

总结

本题的关键点在于理解左叶子结点，如何对左叶子结点进行判断，需要通过父结点，判断其是否为左孩子，再判断是否为叶子结点，算是扩展了一种解题的新思路

找树左下角的值

找树左下角的值

本题中，需要找到左下角的结点，即需要最大深度和最左边的叶子结点，则可以利用先序（中、后序同样也可以）递归遍历的特点，先访问左结点再访问右结点，即只要记录下当前深度和最大深度，若是当前深度大于最大深度，则更新最大深度，并把当前的结点作为左下角的结点；若当前深度等于最大深度，则不更新，因为当前结点仅仅只是最大深度，一定不是左下角的点；若当前深度小于最大深度则同理。

递归法

  1. 确定递归结束条件

    1
    if(!root) return;

  2. 确定返回值

    1
    2
    3
    int res = 0;
    int height = -1;
    void dfs(TreeNode* node, int level)

  3. 单层递归逻辑

    1
    2
    3
    4
    5
    6
    7
    if(level > height)//当前深度为最大深度
    {
    	height = level;
    	res = node->val;
    }
    if(node->left)	dfs(node->left);
    if(node->right)	dfs(node->right);

整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int res = 0;
int height = -1;
    void dfs(TreeNode* node,int level)
    {
        if(!node)   return;
        if(height < level)//如遇到更大深度的，则直接修改res，且只遇到第一个更深的结点才修改
        {
            res = node->val;
            height = level;
        }   
        if(node->left) dfs(node->left,level + 1);
        if(node->right) dfs(node->right,level + 1);
    }
    int findBottomLeftValue(TreeNode* root) {
        if(!root->left&&!root->right)   return root->val;
        dfs(root,1);
        return res;
    }
};

在本题递归解法中，实际上也有使用到回溯的过程，即在判断node->left进入递归时，应对当前深度加一，退出递归后又要将当前深度减一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            depth++;
            traversal(root->left, depth);
            depth--; // 回溯
        }
        if (root->right) {
            depth++;
            traversal(root->right, depth);
            depth--; // 回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

迭代法

层序迭代法更为直观理解，只要在每一层遍历时，存入第一个结点的值即为结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == 0) result = node->val; // 记录最后一行第一个元素
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

总结

两种方法的时间复杂度为O(n)，其中若是链式结构，递归法空间复杂度为O(n)，若是完全二叉树，迭代法空间复杂度O(n/2)。递归法用到了回溯的思想，但可以将其隐藏起来，并不会对结果产生影响。

路径之和

[路径之和](112. 路径总和 - 力扣（LeetCode）)

递归法

很明显这道题需要用到回溯的思想，与寻找二叉树所有路径题相似，通过深度优先遍历递归寻找到一条“路径”（指从根节点到叶子结点的完整路径），再比较路径上结点的值是否与target值相等。需要注意的是在回退上一层父结点时，需要将加入的子结点及时pop出去，即回溯（删除结点）发生在访问到叶子结点的时候。

根据题意，因为要先处理中间结点，更适合用先序遍历

  1. 确定递归结束条件

    因为在进入递归前先判断结点是否为空，则递归结束条件不是结点为空，而是当前结点到达路径终点，即结点是叶子结点

    1
    if(!root->left&&!root->right)

  2. 确定递归返回值

    1
    2
    3
    4
    5
    6
    int lflag = false;
    int rflag = false;
    bool dfs(TreeNode* node,vector<int>& vec,int target)
    {
    	return lflag||rflag;
    }

  3. 确定单层递归逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    vec.push_back(node);
    if(node->left) 
    {
    	lflag = dfs(node->left,vec,target);
    	vec.pop_back();//回溯
    }
    if(node->right)
    {
    	rflag = dfs(node->right,vec,target);
    	vec.pop_back();//回溯
    }

整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int lflag = false, rflag = false;
    bool dfs(TreeNode* node, vector<int>& vec, int target)
    {
        vec.push_back(node->val);
        if (!node->left && !node->right)//遇到叶子结点则路径结束
        {
            if (accumulate(vec.begin(), vec.end(), 0) == target)
                return true;
            return false;
        }
        if (node->left)
        {
            lflag = lflag||dfs(node->left, vec, target);
            vec.pop_back();
        }
        if (node->right)
        {
            rflag = rflag||dfs(node->right, vec, target);
            vec.pop_back();
        }
        return lflag || rflag;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root)  return false;
        vector <int> vec;
        return dfs(root, vec, targetSum);
    }
};

该版本代码在任何情况下都需要遍历所有结点，因此时间复杂度是O(n)，最坏情况下的空间复杂度是O(n)。可以先判断flag的值是否有被修改成true，如果有，则证明存在一条路径符合要求，此时即可直接返回true，只需要添加以下语句

1
if(lflag||rflag) return true;

修改过的版本有类似于平衡二叉树中由底至顶法的意思，一旦遇到有符合的路径就要及时返回，避免额外开销

迭代法

先序迭代遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        stack<pair<TreeNode*, int>> stk;
        stk.push(make_pair(root, root->val));
        while (!stk.empty())
        {
            TreeNode* node = stk.top().first;
            int tmp = stk.top().second;
            stk.pop();
            if (!node->left && !node->right && targetSum==tmp)
            {
                return true;
            }
            if (node->right)
            {
                stk.push(make_pair(node->right, node->right->val + tmp));
            }
            if (node->left)
            {
                stk.push(make_pair(node->left, node->left->val + tmp));
            }
        }
        return false;
    }
};

总结

在递归法中，需要注意与二叉树的所有路径题目不同的是，应该在每次调用递归之后马上进行回溯，即删除结点，这也是个良好的习惯，二叉树的所有路径题中只是因为没有返回值，才导致可以有多个回溯方式，但理论上应统一回溯只发生在递归结束之后。并且根据题目应该遇到合适路径就要立即返回，不需要再做额外的递归开销

在迭代法中，依旧使用stack进行先序遍历，但不能只存储TreeNode*结点，还要存储上当前结点的路径总和值，当遇到叶子结点并且路径总和值与target值相等时，即可直接返回true。其他迭代遍历版本亦是如此

路径之和II

[路径之和](113. 路径总和 II - 力扣（LeetCode）)

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    void dfs(TreeNode* node, vector<int>&path,vector<vector<int>> &res,int target)
    {
        path.push_back(node->val);
        if(!node->left&&!node->right)//遇到叶子结点则当前路径结束
        {
            if(accumulate(path.begin(),path.end(),0)==target)
                res.push_back(path);
            return;
        }
        if(node->left)
        {
            dfs(node->left,path,res,target);
            path.pop_back();//回溯
        }
        if(node->right)
        {
            dfs(node->right,path,res,target);
            path.pop_back();//回溯
        }
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        if(!root)   return res;
        vector<int> path;
        dfs(root,path,res,targetSum);
        return res;
    }
};

总结

与路径之和思路一致，只不过换了方式存储结果和路径结点的值，其他都如出一辙

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

[从中序和后序遍历序列构造二叉树](106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）)

递归法

大致思路如下

  1. 从中序遍历和后序遍历比对，先从后序遍历找到最后一个值，即为根节点的值，在中序遍历序列找到该值并分割

  2. 根据中序遍历分割得到的左右段区间，即为该结点的左右子树，根据左子树区间长度，获取后序遍历中前一部分相等长度的区间，即获得左子树的中序遍历和后序遍历序列，再进入递归运算，返回值作为根节点的左子树；右子树区间同理

  3. 确定递归结束条件

    1
    if(postorder.size()==0)	return nullprt;

    当递归到获取到空的数组时则证明递归结束

  4. 确定递归返回值

    1
    2
    3
    4
    5
    6
    TreeNode* buildtree(vector<int>& inorder,vector<int>& postorder)
    {
    	TreeNode* root = new TreeNode(postorder.back());
    	if(postorder.size()==1)	return root;
    	return root;
    }

    返回当前的结点作为根节点

  5. 确定递归单层逻辑

    1
    2
    root->left = buildtree(**新的中序遍历序列数组**，**新的后序遍历序列数组**);
    root->right = buildtree(**新的中序遍历序列数组**，**新的后序遍历序列数组**);

整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.size()==0) return nullptr;
        TreeNode* root = new TreeNode(postorder[postorder.size()-1]);
        if(postorder.size()==1) return root;
        int i = 0;
        for(i; i < inorder.size(); ++i)
        {
            if(inorder[i]==postorder[postorder.size()-1])
                break;
        }
        vector<int> tmp(inorder.begin(),inorder.begin()+i);
        vector<int> tmp1(postorder.begin(),postorder.begin()+i);
        TreeNode* lnode = buildTree(tmp,tmp1);
        root->left = lnode;
        vector<int> tmp2(inorder.begin()+i+1,inorder.end());
        vector<int> tmp3(postorder.begin()+i,postorder.end()-1);
        TreeNode* rnode = buildTree(tmp2,tmp3);
        root->right = rnode;
        return root;
    }
};

代码较为直观，容易理解，但每次递归都会产生很多新的数组，而且不必要；在寻找i即分割序号时，每次递归都要遍历数组来查找，浪费较多时间。因此，在代码改进上可以只传递两个原有的数组，两组新数组的边界点来达到减少内存开销；通过使用hashmap存储元素和下标实现对时间开销的减少

改进后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    unordered_map<int, int> hashmap;
    int index;
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder, int lboarder, int rboarder)//lboarder代表的是左子树的左边界点，rboarder代表的是右子树的右边界点
    {
        if (rboarder < lboarder) return nullptr;
        int rinb = hashmap[postorder[index]] + 1;
        int linb = hashmap[postorder[index]] - 1;
        TreeNode* root = new TreeNode(postorder[index--]);
        if (rboarder == lboarder) return root;
        //分割点：hashmap[postorder[index]],为根节点
        root->right = traversal(inorder, postorder, rinb, rboarder);
        root->left = traversal(inorder, postorder, lboarder, linb);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = 0;
        index = postorder.size() - 1;
        for (const auto& num : inorder)
        {
            hashmap[num] = i++;
        }
        return traversal(inorder, postorder, 0, inorder.size() - 1);
    }
};

迭代法？？？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) {
            return nullptr;
        }
        auto root = new TreeNode(postorder[postorder.size() - 1]);
        auto s = stack<TreeNode*>();
        s.push(root);
        int inorderIndex = inorder.size() - 1;
        for (int i = int(postorder.size()) - 2; i >= 0; i--) {
            int postorderVal = postorder[i];
            auto node = s.top();
            if (node->val != inorder[inorderIndex]) {
                node->right = new TreeNode(postorderVal);
                s.push(node->right);
            }
            else {
                while (!s.empty() && s.top()->val == inorder[inorderIndex]) {
                    node = s.top();
                    s.pop();
                    inorderIndex--;
                }
                node->left = new TreeNode(postorderVal);
                s.push(node->left);
            }
        }
        return root;
    }
};

总结

递归解法中，解法思路类似于手算构造二叉树过程，但在程序当中，若要低开销的算法，又有很多的小问题小细节需要注意。通常来说，递归解法最好要另外创建一个函数，方便传递不同数量或类型的参数。在本题中，若想要传入数组的大小size，与另一个边界值组成一个区间的形参，如(inorder,postorder,size,lboarder,rboarded)，就要仔细考虑lboarder和rboarder所需要代表是哪一个边界值，如果是左子树的左边界和右子树的右边界点，那么可以得以实现；而如果是左子树的右边界和右子树的左边界，那么无法实现，因为已经知道index代表分割点的位置，即+1或-1就可以知道这两个边界点，两个参数实际上只是一个参数，所以无法实现，必须再传入其他的参数。因此也可以直接传入四个边界点作为形参。

从先序和中序遍历序列构造二叉树

[从先序和中序遍历序列构造二叉树](105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）)

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    unordered_map<int, int> hashmap;
    int index;
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder, int size, int lboarder, int rboarder)
    {
        if (size == 0) return nullptr;
        TreeNode* root = new TreeNode(postorder[index--]);
        if (size == 1) return root;
        //分割点：hashmap[postorder[rboarder]],为根节点
        int lsize = hashmap[postorder[rboarder]];
        int rsize = size - hashmap[postorder[rboarder]] - 1;
        lboarder = hashmap[postorder[rboarder]] - 1;
        rboarder = hashmap[postorder[rboarder]] + 1;
        root->right = traversal(inorder, postorder, rsize, rboarder, rboarder + rsize - 1);
        root->left = traversal(inorder, postorder, lsize, lboarder - lsize + 1, lboarder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = 0;
        index = postorder.size() - 1;
        for (const auto& num : inorder)
        {
            hashmap[num] = i++;
        }
        return traversal(inorder, postorder, postorder.size(), 0, inorder.size() - 1);
    }
};

总结

与上一题思路一样。但能发现，要构造出唯一的二叉树，无论是先序还是后序遍历序列，都必须要有中序遍历序列，这是因为只有中序遍历序列才能得到左右子树的分界线，仅靠先序和后序遍历根本无法得知左右子树的分区间。

最大二叉树

[最大二叉树](654. 最大二叉树 - 力扣（LeetCode）)

递归法

本题中，与构造二叉树题有些许相似，都是需要用到数组的区间来构造二叉树，但这题需要额外找到当前区间的最大值来做根节点并递归

  1. 确定递归结束条件

    1
    if(lboarder>rboarder)	return nullptr;

  2. 确定递归返回值

    1
    2
    3
    4
    TreeNode* traversal(vector<int>&nums,int lboarder,int rboarder)
    {
    	return 根节点;
    }

  3. 确定递归单层逻辑

    1
    2
    3
    //find_maximum并创建根节点root
    root->left = traversal(nums,lboarder,index-1);
    root->right = traversal(nums,index+1,rboarder);

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int root_val;
    int find_maximum(const vector<int>& nums, int l, int r)//返回最大元素的下标值
    {
        root_val = 0;
        int root_index = 0;
        for (int i = l; i <= r; ++i)
        {
            if (nums[i] > root_val)
            {
                root_index = i;
                root_val = nums[i];
            }
        }
        return root_index;
    }
    TreeNode* traversal(vector<int>& nums, int lboarder, int rboarder)
    {
        if (lboarder > rboarder) return nullptr;
        int mid = find_maximum(nums, lboarder, rboarder);
        TreeNode* root = new TreeNode(root_val);
        if (lboarder == rboarder)  return root;

        root->left = traversal(nums, lboarder, mid - 1);
        root->right = traversal(nums, mid + 1, rboarder);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.size() == 1)
        {
            TreeNode* root = new TreeNode(nums[0]);
            return root;
        }
        return traversal(nums, 0, nums.size() - 1);
    }
};

单调栈special解法

针对找到当前最大值元素作为根节点，联想到单调栈实现，并根据在栈中元素关系确定左右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        stack<TreeNode*> stk;
        TreeNode* root = new TreeNode(-1);
        for(int i = 0;i<nums.size();i++)
        {
            TreeNode* node = new TreeNode(nums[i]);
            while(!stk.empty()&&nums[i]>stk.top()->val)//栈顶有元素且比当前元素小，则栈顶元素作当前元素的左子结点
            {
                TreeNode* cur = stk.top();
                stk.pop();
                node->left = cur;
            }
            
            if(!stk.empty())//栈还有元素，则比当前元素大，当前元素为栈顶元素的右子结点
            {
                stk.top()->right = node;
            }
            stk.push(node);
            if(root->val<node->val)
                root = node;
        }
        return root;
    }
};

总结

在递归法中，根据构造二叉树题中的经验，创建额外的递归函数，并以左右子树区间为形参，再将遍历找到最大元素进行函数封装，避免了每次递归创建新的数组的额外开销。时间复杂度为O(n^2)，最坏情况下数组每个元素都会被遍历一次的同时寻找最大元素也会遍历一遍数组，即此时为递增或递减数组；空间复杂度最坏情况下，nums为递减数组或递增数组，需要递归n层，此时空间复杂度为O(n)

针对不断找到最大元素这个点，提出单调栈来优化，在元素存入单调栈的过程中，不断剔除比当前元素小的栈顶元素，并将栈顶元素作为当前元素的左子结点；遇到比当前元素大的栈顶元素，则把当前元素作为栈顶元素的右子结点。时间复杂度为O(n)，数组每个元素最多只被遍历一次；空间复杂度为O(n)，最坏情况下递减或递增数组需要大小为n的栈空间

合并二叉树

递归法

先序遍历递归

  1. 确定递归结束条件

    1
    if(!root1&&!root2)	return nullptr;

  2. 确定递归返回值

    1
    2
    3
    4
    TreeNode* mergeTrees(TreeNode* root1,TreeNode* root2)
    {
    	return root1;	//直接在root1上操作，避免新建树产生的额外开销
    }

  3. 确定递归单层逻辑

    1
    2
    3
    root1->val += root2->val;
    root1->left = mergeTrees(root1->left, root2->left);
    root1->right = mergeTrees(root1->right, root2->right);

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2)  return nullptr;
        if (root1 && !root2) return root1;
        else if (!root1 && root2)  return root2;
        else
            root1->val += root2->val;								//中
        root1->left = mergeTrees(root1->left, root2->left);			  //左
        root1->right = mergeTrees(root1->right, root2->right);		  //右
        return root1;
    }
};

对于中间结点的处理语句，只要更改相对于左右结点处理语句的顺序，就可以实现不同顺序递归遍历二叉树，而不对结果造成影响

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1)  return root2;
        if(!root2)  return root1;
        queue<TreeNode*> que;
        que.push(root1);
        que.push(root2);
        while(!que.empty())
        {
            TreeNode* node1 = que.front();
            que.pop();
            TreeNode* node2 = que.front();
            que.pop();
            node1->val += node2->val;
            if(node1->left&&node2->left)
            {
                que.push(node1->left);
                que.push(node2->left);
            }
            if(node1->right&&node2->right)
            {
                que.push(node1->right);
                que.push(node2->right);
            }
            if(!node1->left&&node2->left)
                node1->left = node2->left;
            if(!node1->right&&node2->right)
                node1->right = node2->right;
        }
        return root1;
    }
};

指针法？？？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void process(TreeNode** t1, TreeNode** t2) {
        if ((*t1) == NULL && (*t2) == NULL) return;
        if ((*t1) != NULL && (*t2) != NULL) {
            (*t1)->val += (*t2)->val;
        }
        if ((*t1) == NULL && (*t2) != NULL) {
            *t1 = *t2;
            return;
        }
        if ((*t1) != NULL && (*t2) == NULL) {
            return;
        }
        process(&((*t1)->left), &((*t2)->left));
        process(&((*t1)->right), &((*t2)->right));
    }
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        process(&t1, &t2);
        return t1;
    }
};

总结

这道题提醒了同时在处理两颗二叉树时的操作，类似于对称二叉树，考虑的需要更加复杂。

二叉搜索树中的搜索

[二叉搜索树中的搜索](700. 二叉搜索树中的搜索 - 力扣（LeetCode）)

根据二叉搜索树的特性，左子结点值小于根节点值小于右子结点值，通过判断当前结点的值与所要求的值的大小，快速找到所要求的值的方向，可以有递归法和迭代法实现

递归法

  1. 确定递归结束条件

    1
    if(!root)	return nullprt;

  2. 确定递归返回值

    1
    2
    3
    TreeNode* searchBST(TreeNode* root,int val)
    if(root->val==val)	return root;
    return nullptr;

  3. 确定递归单层逻辑

1
2
3
if(root->val > val) 		searchBST(root->left, val);
else if(root->val < val)	searchBST(root->right, val);
else	return root;

整体代码如下

1
2
3
4
5
6
7
8
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root)   return nullptr;
        if(root->val==val)  return root;
        return root->val > val? searchBST(root->left,val): searchBST(root->right,val);
    }
};

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
    	TreeNode* node = root;
    	while(node)
    	{
			if(node->val)	return node;
			if(node->val > node)
				node = node->left;
			else if(node->val < node)
				node = node->right;
		}
		return nullptr;
    }
};

总结

根据二叉搜索树的特性，能够极大地简化了代码的复杂程度。在递归法中，由于二叉搜索树有方向性，从而不用考虑是否需要回溯，如平衡二叉树和路径之和题；在迭代法中，二叉搜索树则不需要借助栈或者队列完成对二叉树的遍历，也是因为其特有的方向性。

验证二叉搜索树

[验证二叉搜索树](98. 验证二叉搜索树 - 力扣（LeetCode）)

递归法

对于本题，先想到验证二叉搜索树的方法是 左子结点的值小于根节点的值小于右子结点的值，再对整棵二叉树进行该过程的递归遍历。但这就掉入一个坑中，因为二叉搜索树不仅需要当前的左右子结点与根节点符合规律，还要整棵左右子树都要符合规律，即根节点的左子树上的所有结点都要比根节点要小，同理右子树也是，但这种方法显然无法满足。

因此，借助于中序遍历，若一棵二叉树时二叉搜索树，则中序遍历序列为递增的序列，只要通过一个变量记录最大值，并递归检查当前结点的值是否要比最大值要大，就可以判断是否为二叉搜索树。另外，这个变量为了符合数据大小的要求，结点最小值为INT_MIN，则可以将该变量设为LONG_MIN；或者可以设为前一个结点pre

  1. 确定递归结束条件

    1
    if(!root)	return true

    当前结点为空时，也为二叉搜索树，返回true

  2. 确定递归返回值

    1
    2
    3
    4
    5
    6
    7
    int tmp = LONG_MIN;
    bool isValidBST(TreeNode* root)
    {
    	bool lflag = true,rflag = true;
    	
    	return lflag&&rflag;
    }

  3. 确定递归单层逻辑

    1
    2
    3
    lflag = isValidBST(root->left);
    if(tmp >= root->val)	return false;
    rflag = isValidBST(root->right);

整体代码如下（使用long long变量）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
long long maxi = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(!root)   return true;
        bool lflag = true, rflag = true;
        if(root->left)  lflag = isValidBST(root->left);
        if(root->val > maxi)    
            maxi = root->val;
        else    
            return false;
        if(root->right) rflag = isValidBST(root->right);
        return lflag&&rflag;
    }
};

（使用前一个结点变量）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
TreeNode* pre = nullptr;
    bool isValidBST(TreeNode* root) {
        if(!root)   return true;
        bool lflag = true, rflag = true;
        if(root->left)  lflag = isValidBST(root->left);
        if(!pre||pre->val < root->val)
            pre = root;
        else
            return false;
        if(root->right) rflag = isValidBST(root->right);
        return lflag&&rflag;
    }
};

迭代法

使用中序迭代遍历法，只需稍微修改即可,对应地，迭代法也可以用一个long long变量或者前一个结点来存储最大值，下面只给出long long变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root)   return true;
        stack<TreeNode*> stk;
        TreeNode* node = root;
        long long tmp = LONG_MIN;
        while(!stk.empty()||node)
        {
            if(node)
            {
                stk.push(node);
                node=node->left;
            }
            else
            {
                node = stk.top();
                stk.pop();
                if(tmp >= node->val)
                    return false;
                tmp = node->val;
                node = node->right;
            }
        }
        return true;
    }
};

总结

为了验证一棵二叉搜索树，要将其当成一棵普通二叉树来看待，就不能利用二叉搜索树的特性。在判断时，需要注意左子树小于根节点小于右子树，而不只是单单的左子结点小于根节点小于右子结点，再结合中序遍历，可以利用严格单调有序性来判断一棵树是否为二叉搜索树，这时就要用到一个变量来记录当前下的最大结点值，结合所给定数据范围，可以将这个变量设为LONG_MIN来完成所有INT数据的测试；但如果测试数据中出现了LONG型数据，那可以将这个变量设为一个树的结点类型，用于存储前一个结点，这就不用考虑数据的类型和大小范围。

对于迭代法，则是基于中序迭代遍历模板的改变版，同样也有两种不同类型变量。两种方法的时间复杂度和空间复杂度都是O(n)，最坏情况下是一条链。

二叉搜索树的最小绝对差

[二叉搜索树的最小绝对差](530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）)

递归法

根据题意，因为是任意两个结点的差，依旧可以使用中序遍历的方法对二叉树进行遍历，且因为中序遍历序列严格单调递增，则可以通过对相邻两个结点的值进行判断来获取最小绝对差。此外，该题中，既可以先用数组存储所有结点的值，再遍历一次数组进行判断；也可以通过一个结点变量，记录前一个结点的值，从而在遍历二叉树过程中就完成对绝对差的记录

中序递归遍历+转换成数组计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> res;
int ans = INT_MAX;
    void dfs(TreeNode* root)
    {
        if(!root)   return;
        if(root->left)  dfs(root->left);
        res.push_back(root->val);
        if(root->right) dfs(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        dfs(root);
        int i = 1, j = 0;
        for(i,j;i<res.size();i++,j++)
        {
            ans = min(ans,abs(res[i]-res[j]));
        }
        return ans;
    }
};

记录前一个结点与当前结点进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int res = INT_MAX;
    int pre = -1,cur = -1;
    int getMinimumDifference(TreeNode* root) {
        if (!root)   return 0;
        if (root->left)
        {
            cur = root->left->val;
            getMinimumDifference(root->left);
        }
        cur = root->val;
        //if(pre!=-1)即可
        if (pre!=-1&&abs(cur - pre))
            res = min(abs(cur - pre), res);
        pre = cur;
        if (root->right) getMinimumDifference(root->right);
        return res;
    }
};

当然，在以上的程序中，也可以沿用上题中的两种方式，一种是用一个整型变量来记录前一个结点的值（如上）；另一种是用一个TreeNode*变量来记录前一个结点。后者只需要在更新res时将判断条件修改为if(pre)本质上都是一样

迭代法

依旧使用中序遍历迭代法，基于模板上修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        int ans = INT_MAX;
        TreeNode* node = root;
        while(!stk.empty()||node)
        {
            if(node)
            {
                stk.push(node);
                node = node->left;
            }
            else
            {
                node = stk.top();
                stk.pop();
                res.push_back(node->val);
                node = node->right;
            }
        }
        for(int i=0,j=1;j<res.size();++j,++i)
        {
            ans = min(ans,abs(res[i]-res[j]));
        }
        return ans;
    }
};

同样，迭代法中也可以不用新建一个数组，最后再遍历一次数组得到答案，也是设定前一个结点，可以是整型变量存结点的值，也可以直接存一个结点来实现

总结

本题与上一题验证二叉搜索树的遍历思路一致，只是上题判断前后两者大小关系，本题计算前后两者大小并取最小值

二叉搜索树中的众数

[二叉搜索树中的众数](501. 二叉搜索树中的众数 - 力扣（LeetCode）)

从寻找众数角度出发，通常需要借助一个数组或哈希表等来存储元的值以及对应的出现次数，先遍历一遍二叉树得到存储整棵树的数组或哈希表，再将数组或哈希表进行排序，取出排序最大的一个或多个元素，存入到结果当中。而这就需要O(N)的时间复杂度，最坏情况下所有元素都只出现一次，时间复杂度是O(2N)，空间复杂度也会很大。

上述方法仅对一般的二叉树，但在本题中是一颗二叉搜索树，也就是说是一棵已经排好序的二叉树，相同的值的结点都是邻接在一起的，因此，仅需要一次遍历，通过pre指针指向上一个结点，与当前结点比较，并统计相同值结点的个数，就能找出其众数

递归法

  1. 确定递归结束条件

    1
    if(!node)	return;

  2. 确定递归返回值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int times = 0, ttimes = 0;
    vector<int> res;
    TreeNode* pre = nullptr;
    void dfs(TreeNode* node)
    {
    	dfs(node->left);
    	//根结点
    	dfs(node->right);
    }

  3. 确定递归单层逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    if (pre && pre->val != node->val)
    {
        ttimes = 0;
    }
    if (pre && pre->val == node->val)
    {
        ++ttimes;
    }
    if (ttimes == times)
    {
        res.push_back(node->val);
    }
    if (ttimes > times)
    {
        times = ttimes;
        res.clear();
        res.push_back(node->val);
    }

整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<int> res;
    TreeNode* pre = nullptr;
    int times = 0;
    int ttimes = 0;
    void dfs(TreeNode* node)
    {
        if (!node)   return;
        dfs(node->left);
        if (pre && node->val != pre->val)
        {
            ttimes = 0;
        }
        if (pre && pre->val == node->val)
        {
            ++ttimes;
        }
        if (ttimes == times)
        {
            res.push_back(node->val);
        }
        if (ttimes > times)
        {
            res.clear();
            times = ttimes;
            res.push_back(node->val);
        }
        pre = node;
        dfs(node->right);
    }
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return res;
    }
};

迭代法

同样地，用中序迭代遍历法，而处理根结点代码与递归法中的一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        TreeNode* node = root;
        TreeNode* pre = nullptr;
        int times = 0, ttimes = 0;
        while(!stk.empty()||node)
        {
            if(node)
            {
                stk.push(node);
                node = node->left;
            }
            else
            {
                node = stk.top();
                stk.pop();
                if(pre&&pre->val!=node->val)
                {
                    ttimes = 0;
                }
                if(pre&&pre->val == node->val)
                {
                    ++ttimes;
                }
                if(ttimes==times)
                {
                    res.push_back(node->val);
                }
                if(ttimes>times)
                {
                    times = ttimes;
                    res.clear();
                    res.push_back(node->val);
                }
                pre = node;
                node = node->right;
            }
        }
        return res;
    }
};

总结

对本题而言，依旧是对pre指针和cur指针的同时运用，这一点上与前两题都一致，不同的是本题还需要对pre和cur指向的结点的值出现次数进行统计，而在统计这里提出针对一般情况和针对二叉搜索树的不同解法，一般情况下借助于特殊的数据结构来对元素的值及其出现次数进行统计，但在二叉搜索树下则不用，因为其本身就已经是排序好的。若是针对一般情况下，有其他数据结构支撑的，可以选取任意的遍历顺序，但针对二叉搜索树时，为了运用到它的有序性，通常都会用中序遍历，也只有中序遍历序列是有序的。在迭代法中，无非就是在处理根结点的代码上将递归法的代码照搬过来，套用在模板上。

二叉树的最近公共祖先

[二叉树的最近公共祖先](236. 二叉树的最近公共祖先 - 力扣（LeetCode）)

最近公共祖先可简化成两种情况，一种是直接找到除要寻找的两结点之外的第三结点作为两结点的公共祖先，即要返回该第三结点作为结果；另一种则是其中一个结点是另一结点的祖先，则返回该结点作为结果即可。

递归法

根据题意，这题可以用到回溯法，由于后续遍历本身就是回溯（左右中），可以先判断左右子树是否有包含要找的结点，再来判断当前结点是否是公共祖先。同时，这也是一种由底至顶的方法。

  1. 确定递归结束条件

    1
    2
    if(!root)	return nullptr;
    if(root==q||root==p) return root;

  2. 确定递归返回值

    1
    2
    3
    4
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
    	return nullptr;
    }

当当前结点即为要寻找的结点时，即可直接返回当前结点，向上回溯；如果没有找到，则返回空结点

  1. 确定递归单层逻辑

    1
    2
    3
    4
    5
    6
    TreeNode* ltree = lowestCommonAncestor(root->left,p,q);				//左
    TreeNode* rtree = lowestCommonAncestor(root->right,p,q);			//右
    if(ltree&&rtree)	return root;								  //中
    else if(!ltree&&rtree)	return rtree;
    else if(ltree&&rtree)	return ltree;
    return nullptr;

    如果当前的根节点的左子结点和右子结点的返回值不为空（返回值为p和q），则证明当前的根节点就是他们的公共祖先，直接返回根节点；如果当前结点的左子结点为空，但右子结点不为空，则证明p或q在右子结点，直接返回右子结点；右子结点为空同理；最后，都没有找到则证明p和q都不在当前结点的子树下，返回空结点

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)   return NULL;
        if(root==p||root==q)    return root;
        TreeNode* ltree = lowestCommonAncestor(root->left,p,q);
        TreeNode* rtree = lowestCommonAncestor(root->right,p,q);
        if(ltree&&rtree) 
            return root;
        else if(ltree&&!rtree) 
            return ltree;
        else if(!ltree&&rtree)
            return rtree;
        return NULL;
    }
};

递归hashmap查表法

不边递归回溯边记录判断，则需要独立遍历一次二叉树，借助unordered_map<int,TreeNode*> fanode进行父结点的记录，再将p或q通过fanode向上查询父结点，借助另一个unordered_map<int,bool> cmp进行有无相同父结点的判断

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
unordered_map<int,TreeNode*> fanode;
unordered_map<int,bool> cmp;
    void dfs(TreeNode* root)
    {
        if(root->left)
        {
            fanode[root->left->val] = root;
            dfs(root->left);
        }
        if(root->right)
        {
            fanode[root->right->val] = root;
            dfs(root->right);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fanode[root->val] = NULL;
        dfs(root);
        while(p)
        {
            cmp[p->val]=true;
            p=fanode[p->val];
        }
        while(q)
        {
            if(cmp[q->val])
                return q;
            q = fanode[q->val];
        }
        return NULL;
    }
};

遍历每个结点获取对应父结点需要时间O(n)，在向上寻找p、q共同父结点时，遍历的结点数不会超过n，最坏情况下是树单独成链，总的时间复杂度是O(n)，且接近O(2n)；对于递归遍历每个结点所占用的递归栈空间最坏情况下为O(n)，而储存n个结点的哈希表空间复杂度也为O(n)，因此总的空间复杂度为O(3n)，性能与第一种解法无量级上的差异但比第一种解法要差

总结

通用解法是在递归的过程中直接记录和处理，这就省去了额外的时间和空间开销。在处理最近公共祖先问题上，最先想到应该由底至顶的遍历二叉树，即回溯，而后序遍历又是天生的回溯顺序。这一点上与相同用到回溯法的平衡二叉树题一致，都用到后序遍历；但在有关二叉树路径题中，因为递归的过程需要先处理根结点，所以用的是先序遍历回溯。

回溯递归使用先序遍历中，通过成员变量快速判断有无符合条件的情况发生，可以直接向上回溯，如路径之和；而使用后序遍历，都要先遍历完所有的结点，因为要用到处理结点后的返回值，先进入递归才能再判断有无发生，如由底至顶的平衡二叉树。

if(root==q||root==p) return root;这是对结束条件的补充，为的是遇到想要查找的结点时及时返回，获取返回值，并且不必继续做无谓的遍历直至叶子结点

递归法中对于情况二的处理，只分开根结点的左、右子树作为查找对象，即在一个子树上只寻找一个目标结点，（情况二则是两个目标结点都在一个子树上，且以其中一个结点作为公共祖先返回结果），因此一旦找寻到其中一个结点，即可直接返回该结点，也正是目标结点的公共祖先。

二叉搜索树的最近公共祖先

[二叉搜索树的最近公共祖先](235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）)

递归法

明显这道题与上题相比，需要用到二叉搜索树的特性，即有序性。

因为是要寻找公共祖先，是由底至顶的查找，所以要用后序遍历，同时符合了回溯的要求。

  1. 确定递归结束条件

    1
    if(!root)	return root;

    也可以不写，因为题目保证了能够找得到公共祖先

  2. 确定递归返回值

    1
    2
    3
    4
    5
    6
    TreeNode* lflag = NULL,*rflag = NULL;
    TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q)
    {
    	if(lflag||rflag)	return lflag==NULL?rflag:lflag;
    	return root;										//中
    }

    如果找到p或q则返回当前结点；如果lflag或rflag被赋值，证明找到p或者q，则返回被赋值的那个flag

  3. 确定递归单层逻辑

    1
    2
    3
    4
    if(q->val < root->val && p->val < root->val)
    	lflag = lowestCommonAncestor(root->left,p,q);			//左
    if(q->val > root->val && q->val > root->val)
    	rflag = lowestCommonAncestor(root->right,p,q);			//右

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
TreeNode* lflag=NULL, *rflag=NULL;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)   return root;
        if(p->val < root->val&&q->val < root->val)
        {
            rflag = lowestCommonAncestor(root->left,p,q);
        }
        if(p->val > root->val&&q->val > root->val)
        {
            lflag = lowestCommonAncestor(root->right,p,q);
        }
        if(lflag||rflag)    return lflag==NULL?rflag:lflag;
        return root;
    }
};

迭代法

在上述递归的过程中，其实就是迭代的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* res = root;
        while(res)
        {
            if(res->val > p->val&&res->val > q->val)
                res = res->left;
            else if(res->val < p->val&&res->val < q->val)
                res = res->right;
            else
                return res;
        }
        return NULL;
    }
};

总结

在递归法中，首先，当q->val < root->val && p->val > root->val或者q->val > root->val && p->val < root->val，换句话说，当当前结点值处于p和q值的区间内，那么当前结点就一定是p和q的最近公共祖先（有序性）。其次，因为是一定能够找到公共祖先，所以单层逻辑中对中间结点的处理就是递归的返回值——直接返回当前结点（即公共祖先），这也是递归的最深一层。

相对于普通的二叉树，在寻找二叉搜索树的最近公共祖先时，可以更加的有方向性去寻找所要的结点，不需要遍历所有结点，而当找到所要找的结点时，由于没有多余遍历其他结点，也就不会遇到返回值为空的结点，对有返回值的结点处理也更加简洁（只在lflag或rflag中，直接返回结果就行），因此实际上并没使用到回溯。因为没有遍历所有结点，空间复杂度为O(1)

同样地，二叉搜索树的最近公共祖先也有两种情况，一种是直接找到除要寻找的两结点之外的第三结点作为两结点的公共祖先，即要返回该第三结点作为结果；另一种则是其中一个结点是另一结点的祖先，则返回该结点作为结果即可。对于第二种情况，只要不满足p和q结点值同时大于或者小于当前结点的值，就直接返回当前结点，而当前结点也正是它们的共同祖先（其中一个结点本身）

另外，该题也可以用普通二叉树的最近公共祖先两种做法

二叉搜索树的插入操作

[二叉搜索树中的插入操作](701. 二叉搜索树中的插入操作 - 力扣（LeetCode）)

递归法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root)   
            return new TreeNode(val);
        if(val < root->val)
            root->left = insertIntoBST(root->left,val);
        else if(val > root->val)
            root->right = insertIntoBST(root->right,val);
        return  root;
    }
};

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* newnode = new TreeNode(val);
        TreeNode* node = root;
        if(!node)
        {
            return newnode;
        }
        while(node)
        {
            if(val < node->val&&node->left)
                node = node->left;
            else if(val > node->val&&node->right)
                node = node->right;
            else if(val < node->val&&!node->left)
            {
                node->left = newnode;
                node = newnode->left;
            }
            else if(val > node->val&&!node->right)
            {
                node->right = newnode;
                node = newnode->right;
            }
        }
        return root;
    }

总结

本题还有重新构建二叉搜索树的方法，但在本解法中只做了直接向二叉搜索树添加新结点的做法，并没有手算向二叉搜索树插入操作的代码实现方法

删除二叉搜索树中的结点

[删除二叉搜索树中的结点](450. 删除二叉搜索树中的节点 - 力扣（LeetCode）)

对回溯法的理解

首先，要做的第一步是 找到要删除结点的父结点，利用递归回溯的思想，借助栈保存当前访问结点的父结点，一旦确定当前结点是要删除的结点，则栈顶元素就是其父结点。因为要找根结点，因此选择了先序递归遍历。但缺点在于无论什么时候找到要目标结点，都会遍历整棵二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool find_fa_dfs(int key, stack<TreeNode*> & stk)
{
    TreeNode* tmp = stk.top();
    if (tmp->val == key)
    {
        return true;
    }
    if (tmp->left)
    {
        stk.push(tmp->left);
        if (find_fa_dfs( key, stk))
            fa = tmp;
        stk.pop();
    }
    if (tmp->right)
    {
        stk.push(tmp->right);
        if (find_fa_dfs( key, stk))
            fa = tmp;
        stk.pop();
    }
    return false;
}

对于代码中的改进点，要求当找到目标结点后要及时返回或结束递归，可加上一个判断，if(fa!=nullptr)return false;当找到了目标结点，fa结点就会被修改，因此对于遍历中不在回溯路径上的后续结点，当进入递归时就会直接返回。但如果目标结点是根结点fa=nullptr，则无效，依旧会遍历整棵二叉树。

另外，题中这是一颗二叉搜索树，则可以利用其特性快速找到目标结点及其父结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode* fa = nullptr;
void find_fa_dfs(TreeNode* node,int key)
{
    TreeNode* lnode = nullptr, * rnode = nullptr;
    if (!node)   return;
    if (node->val < key)
    {
        fa = node;
        find_fa_dfs(node->right, key);
    }
    else if (node->val > key)
    {
        fa = node;
        find_fa_dfs(node->left, key);
    }
    else
        return;
}

递归法

  1. 确定递归结束条件

    1
    if(!root)	return nullptr;

  2. 确定递归返回值

    1
    2
    3
    4
    5
    TreeNode* deleteNode(TreeNode* root,int key)
    {
    	
    	return root;
    }

  3. 确定单层逻辑

    在本题中，关键在于对不同情况的分类讨论

    • 当前结点为空，直接返回空结点
    • 当前结点值比key大，递归进入当前结点的左子结点
    • 当前结点值比key小，递归进入当前结点的右子结点
    • 当前结点值等于key值，则证明找到目标删除结点
      • 目标结点是叶子结点，直接删除，返回空结点
      • 目标结点有单孩子结点，孩子结点补上，作为根节点返回
      • 目标结点有两个孩子结点，将目标结点的左孩子结点作为目标结点的右孩子结点的最左下叶子结点的左子树，右孩子结点作为根结点返回
    • 都不符合，则是key不存在于当前树中，无需删除，返回root

    整体代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            if (!root)   return root;
            if (root->val < key)
            {
                root->right = deleteNode(root->right, key);
                return root;
            }
            else if (root->val > key)
            {
                root->left = deleteNode(root->left, key);
                return root;
            }
            else
            {
                if (!root->left && !root->right)
                {
                    delete root;
                    return nullptr;
                }
                else if (!root->right)
                    return root->left;
                else if (!root->left)
                    return root->right;
                else
                {
                    TreeNode* tmp = root->right;
                    while (tmp->left)
                    {
                        tmp = tmp->left;
                    }
                    tmp->left = root->left;
                    TreeNode* node = root;
                    root = root->right;
                    delete node;
                    return root;
                }
            }
            return root;
        }
    };

    重要的是，理解在每次调用递归时，返回的值是作为当前结点下删除目标结点后的新的子树

迭代法

模拟实现递归的过程，但会因为在分类讨论下，多出了判断当前结点是否为二叉搜索树的根结点，从而导致代码出现很多重复，也可以封装成一个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root)   return root;
        TreeNode* node = root, * fa = nullptr;
        while (node)
        {
            if (key < node->val)
            {
                fa = node;
                node = node->left;
            }
            else if (key > node->val)
            {
                fa = node;
                node = node->right;
            }
            else if (key == node->val)
            {
                if (!node->left && !node->right)
                {
                    if(!fa) return nullptr;
                    if(fa->val > key)
                        fa->left = nullptr;
                    else
                        fa->right = nullptr;
                    delete node;
                    return root;
                }
                else if (!node->left)
                {
                    if(!fa)
                        return node->right;
                    if (fa->val > key)
                        fa->left = node->right;
                    else
                        fa->right = node->right;
                    delete node;
                    return root;
                }
                else if (!node->right)
                {
                    if(!fa)
                        return node->left;
                    if (fa->val > key)
                        fa->left = node->left;
                    else
                        fa->right = node->left;
                    delete node;
                    return root;
                }
                else
                {
                    TreeNode* lnode = node->left;
                    TreeNode* tmp = node->right;
                    while (tmp->left)
                    {
                        tmp = tmp->left;
                    }
                    tmp->left = lnode;
                    if (!fa)
                    {
                        node = node->right;
                        return node;
                    }
                    if (fa->val > key)
                        fa->left = node->right;
                    else
                        fa->right = node->right;
                    delete node;
                    return root;
                }
            }
        }
        return root;
    }
};

总结

对于本题中的递归法，类似其他二叉搜索树的题目，都能用到递归算法，且可以利用二叉搜索树的特性简化递归过程。这一题考查了分类讨论的多种情况，并要求在递归遍历找到目标删除结点的父结点，或根据返回值对父结点的指向作更新。同时，对比迭代法，因为不能用返回值不断向上返回新的根结点，迭代法需要找到目标结点的父结点，才能修改删除结点后父结点的指向，可得知，用函数封装后的返回值可以简便的修改二叉树结构。

在力扣编译器中，就算是叶子结点，直接将其delete掉也会报错，需要把其父结点更改为指向空结点，即断开跟不删除结点的所有连接才能不报错

递归法和迭代法的时间复杂度都是O(n)，遍历一次二叉树的结点。递归法的空间复杂度最坏情况下是O(n)，迭代法的空间复杂度是O(1)，只占用常量级的空间，因为二叉搜索树的迭代不需要用到栈或队列

修剪二叉搜索树

[修剪二叉搜索树](669. 修剪二叉搜索树 - 力扣（LeetCode）)

递归法

类比上一题，后序遍历所有二叉树结点，并将修剪过后的子树的根结点作为返回值，作为根结点的新左子结点或者新右子结点。如果当前结点值小于要求范围，根据二叉搜索树的特性，从当前结点的右子树不断向右寻找，直到值在要求范围内，并返回该结点；如果当前结点值大于要求范围，也同理

  1. 确定递归结束条件

    1
    if(!root)	return nullptr;

    当遇到空结点时返回空结点

  2. 确定递归返回值

    1
    2
    3
    4
    5
    6
    TreeNode* trimBST(TreeNode* root, int low, int high)
    {
    	root->left = trimBST(root->left,low,high);
    	root->right = trimBST(root->right,low,high);
    	return root;
    }

    让左子结点进入递归，并将新的结点作为返回值，给该结点的左子结点重新赋值

    右子结点同理

    全部子树修剪完成，则返回根结点

  3. 确定递归单层逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    if(root->val < low)
    {
    	TreeNode* tmp = root->right;
    	while(tmp && tmp->val < low)
    	{
    		tmp = tmp->right;
    	}
    	return tmp == nullptr?nullptr:tmp;
    }
    //另一边同理

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root)   return root;
        //后序遍历
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        if (root->val < low)
        {
            TreeNode* tmp = root->right;
            while (tmp && tmp->val < low)
            {
                tmp = tmp->right;
            }
            return tmp == nullptr ? nullptr : tmp;
        }
        if (root->val > high)
        {
            TreeNode* tmp = root->left;
            while (tmp && tmp->val > high)
            {
                tmp = tmp->left;
            }
            return tmp == nullptr ? nullptr : tmp;
        }
        return root;
    }
};

这个版本的递归中，每个结点都进入了递归，其实不需要，只是将符合范围的当前结点的左右结点送入递归即可，但不能够直接改成

1
2
3
4
5
if(root->val > low && root->val < high)
{
	root->left = trimBST(root->left,low,high);
	root->right = trimBST(root->right,low,high);
}

因为后面在处理中间结点的代码，相当于循环迭代处理，没有保证到根结点的子树都会进入递归，因此，可以将中间结点的处理过程修改成递归形式，整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root)   return root;
        if(root->val >= low && root->val <= high)
        {
            root->left = trimBST(root->left,low,high);
            root->right = trimBST(root->right,low,high);
        }
        if(root->val < low)
        {
            return trimBST(root->right,low,high);
        }
        if (root->val > high)
        {
            return trimBST(root->left,low,high);
        }
        return root;
    }
};

问题在于，会导致占用更多的栈空间，让整个程序的空间复杂度比原有的更加大。

综上所述，第一个版本的递归由于带上了部分迭代的版本，总体性能更优

迭代法

类似上一题删除二叉搜索树中的结点，迭代法需要找到目标结点的父结点，并改变父结点的指向，在本题中，需要先循环寻找到在范围之内的根结点，再分别对左子树和右子树进行循环判断和更改，循环过程是关键

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root)   return root;
        while(root&&(root->val < low || root->val > high))
        {
            if(root->val < low)
                root = root->right;
            else
                root = root->left;
        }
        TreeNode* node = root;
        while(node)
        {
            while (node->right && node->right->val > high)
            {
                node->right = node->right->left;
            }
            node = node->right;
        }
        node = root;
        while(node)
        {
            while (node->left && node->left->val < low)
            {
                node->left = node->left->right;
            }
            node = node->left;
        }
        
        return root;
    }
};

总结

这两题中，迭代法由于不占用递归栈的空间，空间复杂度都为O(1)，但需要考虑的情况更加多，比递归法更为复杂

将有序数组转换成二叉搜索树

[将有序数组转换成二叉搜索树](108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）)

递归法

  1. 确定递归结束条件

    1
    if(start<end)	return nullptr;

  2. 确定递归返回值

    1
    2
    3
    4
    5
    TreeNode*(vector<int>&nums,int start,int end)
    {
    	
    	return root;
    }

  3. 确定递归单层逻辑

    1
    2
    3
    TreeNode* root = new TreeNode(nums[(left + right + 1)/2]);
    root->left = sortedArrayIndexToBST(nums, start, rootindex - 1);
    root->right = sortedArrayIndexToBST(nums, rootindex + 1, end);

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* sortedArrayIndexToBST(vector<int>& nums, int start, int end)
    {
        if (end < start)   return nullptr;
        int rootindex = (end+start+1) / 2;
        TreeNode* root = new TreeNode(nums[rootindex]);
        root->left = sortedArrayIndexToBST(nums, start, rootindex - 1);
        root->right = sortedArrayIndexToBST(nums, rootindex + 1, end);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==1)  
            return new TreeNode(nums[0]);
        return sortedArrayIndexToBST(nums,0,nums.size()-1);
    }
};

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        queue<pair<TreeNode*, int>> que;     //父结点和index
        TreeNode* root = new TreeNode(0);
        que.push(make_pair(nullptr, nums.size() / 2));

        while (!que.empty())
        {
            int index = que.front().second;
            TreeNode* fa = que.front().first;
            que.pop();

            TreeNode* cur = new TreeNode(nums[index]);
            if (fa && nums[index] < fa->val)
                fa->left = cur;
            else if (fa && nums[index] > fa->val)
                fa->right = cur;
            else
                root = cur;
            if (index - 1 >= 0) que.push(make_pair(cur, index / 2));
            if (index + 1 < nums.size())   que.push(make_pair(cur, (index + nums.size() + 1) / 2));
        }
        return root;
    }
};

以上版本的代码会死循环，原因在于条件判断进入队列，由于子区间没有边界限定，而只使用原始nums的边界，就会导致一直有实际上并不合法的结点进入队列。此时，需要有额外的容器去记录边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;

        TreeNode* root = new TreeNode(0);   // 初始根节点
        queue<TreeNode*> nodeQue;           // 放遍历的节点
        queue<int> leftQue;                 // 保存左区间下标
        queue<int> rightQue;                // 保存右区间下标
        nodeQue.push(root);                 // 根节点入队列
        leftQue.push(0);                    // 0为左区间下标初始位置
        rightQue.push(nums.size() - 1);     // nums.size() - 1为右区间下标初始位置

        while (!nodeQue.empty()) {
            TreeNode* curNode = nodeQue.front();
            nodeQue.pop();
            int left = leftQue.front(); leftQue.pop();
            int right = rightQue.front(); rightQue.pop();
            int mid = left + ((right - left) / 2);

            curNode->val = nums[mid];       // 将mid对应的元素给中间节点

            if (left <= mid - 1) {          // 处理左区间
                curNode->left = new TreeNode(0);
                nodeQue.push(curNode->left);
                leftQue.push(left);
                rightQue.push(mid - 1);
            }

            if (right >= mid + 1) {         // 处理右区间
                curNode->right = new TreeNode(0);
                nodeQue.push(curNode->right);
                leftQue.push(mid + 1);
                rightQue.push(right);
            }
        }
        return root;
    }
};

总结

这道题也属于修改二叉搜索树的结构，通常在处理中间结点后，可以利用递归返回值来更新二叉搜索树的左右结点，并递归下去

且迭代法要考虑的比递归法要复杂很多，在本题中，迭代法最终实现过程还是依据了递归法的过程，用边界条件作为参数，不断缩小边界，只不过在递归法中使用函数的传参代替了迭代法中用于记录这几个参数的容器

把二叉搜索树转换成累加树

[把二叉搜索树转换成累加树](538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）)

递归法

灵活运用遍历顺序，根据题意，需要找最大的结点，即最右结点，再访问第二大的结点，即中间结点，最后才是左结点，实际上这就是中序遍历的逆序

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int res = 0;
    TreeNode* convertBST(TreeNode* root) {
        if(!root)   return nullptr;
        convertBST(root->right);
        res += root->val;
        root->val = res;
        convertBST(root->left);
        return root;
    }
};

迭代法

迭代法所用到的也是中序遍历的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if(!root)   return nullptr;
        int sum = 0;
        stack<TreeNode*> stk;
        TreeNode* node = root;
        while(!stk.empty()||node)
        {
            if(node)
            {
                stk.push(node);
                node = node->right;
            }
            else
            {
                node = stk.top();
                stk.pop();
                sum += node->val;
                node->val = sum;
                node = node->left;
            }
        }
        return root;
    }
};

总结

第一想法是，第一次遍历二叉树，借助数组存储每个结点的值，再遍历一次数组，对数组的值进行处理，使得每个下标对应的是累加后的数值，最后遍历一次二叉树修改原值。

这一题摆脱了常规的遍历顺序，尝试了先访问右结点的逆向中序遍历

LeetCode贪心算法章节
https://kevin346-sc.github.io/2022/10/15/LeetCode二叉树章节/
作者
Kevin Huang
发布于
2022年10月15日
许可协议