当前位置:   article > 正文

14、指针三剑客之二:树(结合LeetCode 104、110、543、437、101、1110、637、105、144、99、669、208学习)(99未进阶)(前缀树)_指针三剑客之三

指针三剑客之三

作者学习算法的教材是LeetCode 101

有需要的同学直接GitHub搜索LeetCode 101即可 **

一、树的递归

104. 二叉树的最大深度(难度:简单)

  • 利用递归,代码如下:
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return root ? 1 + max(maxDepth(root->left) , maxDepth(root->right)) : 0;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

110. 平衡二叉树(难度:简单)

  • 利用递归
  • 每棵子树进行abs(left - right)判断,若大于一,则返回-1,否则返回子树最大深度;
  • 若子树中有值为-1的子树,说明该子树的子树已经不平衡,直接返回-1即可;
  • 代码如下:
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (helper(root) != -1){
            return true;
        }
        else {
            return false;
        }
    }

    int helper(TreeNode* root) {
        if (!root) {
            return 0;
        }
        int left = helper(root->left);
        int right = helper(root->right);
        if (left == -1 || right == -1 || abs(left - right) > 1) {
            return -1;
        }
        return 1 + max(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

543. 二叉树的直径(难度:简单)

  • 利用count记录已搜索过的最大直径;
  • count每次记录的最大直径和递归返回的值不同,最大直径是树两侧结点的最长距离,递归返回的是树某侧的最大深度;
  • 然后用树左右两侧的最大深度想加就是某节点的最大直径,与count比较,count记录更大值;
  • 代码如下:
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int count = 0;
        helper(root , count);
        return count;
    }

    int helper(TreeNode* root , int& count) {
        if  (!root) {
            return 0;
        }
        int left = helper(root->left , count);
        int right = helper(root->right , count);
        count = max(left + right , count);
        return 1 + max(left , right);
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

437. 路径总和Ⅲ(难度:中等)

  • 使用两次递归,第一次递归是pathsum(),表示从每个节点开始有无目标路径;
  • 第二次递归是pathSumStartWithRoot(),参数sum是用sum - root->val的值,用count记录目标路径数,如果此时指向的节点值正好等于sum(sum已经减去前几部分节点值)表明这是一条目标路径,count返回1,否则count返回0;
  • 代码如下:
class Solution { 
public:
    int pathSum(TreeNode* root, int sum) {
        return root ? pathSumStartWithRoot(root , sum) + pathSum(root->left , sum) + pathSum(root->right , sum) : 0;
    }

    int pathSumStartWithRoot(TreeNode* root , int sum) {
        if (!root) {
            return 0;
        }
        int count = root->val == sum ? 1 : 0;
        count += pathSumStartWithRoot(root->left , sum - root->val);
        count += pathSumStartWithRoot(root->right , sum - root->val);
        return count;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

101.对称二叉树(难度:简单)

  • 判断对称或者两个子树是否相等,“四步法”:
  • 若两子树都为空,则对称;若只有一个为空,则不对称;若两子树值不同,则不对称;根据相等或对称,做递归处理;
  • 代码如下:
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return !root ? true : isSymmetric(root->left , root->right);
    }

    bool isSymmetric(TreeNode* left , TreeNode* right) {
        if (!left && !right) {
            return true;
        }
        if (!left || !right) {
            return false;
        }
        if (left->val != right->val) {
            return false;
        }
        return isSymmetric(left->left , right->right) && isSymmetric(left->right , right->left);
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

1110. 删点成林(难度:中等)

  • 自下而上处理不到根节点,所以根节点要在主函数中单独处理;
  • 使用set集合保存待删除结点,以空间换时间;
  • vector<TreeNode*>类型的变量,类似于vector<vector>类型的变量,即存入一个链表节点后,会将其之后所连接的结点一并存入;(纯属我自己的理解,若有误,请狠狠的批评
  • 代码如下:
class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        set<int> dict(to_delete.begin() , to_delete.end());//以空间换时间
        vector<TreeNode*> forest;
        root = helper(root , dict , forest);
        if (root) {
            forest.push_back(root);
        }
        return forest;
    }

    TreeNode* helper(TreeNode* root , set<int> &dict , vector<TreeNode*> &forest) {
        if (!root) {
            return root;
        }
        root->left = helper(root->left , dict , forest);
        root->right = helper(root->right , dict , forest);
        if (dict.count(root->val)) {
            if (root->left) {
                forest.push_back(root->left);
            }
            if (root->right) {
                forest.push_back(root->right);
            }
            root = nullptr;
        }
        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

二、层次遍历

637. 二叉树的层平均值(难度:简单)

  • 用队列queue实现广度优先搜索;
  • 首先根节点进入,然后计算队列长度,将一层的节点全部遍历后释放,并将下一层节点全部装入到队列中,知道所有节点全部遍历完毕;
  • 代码如下:
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> q;
        vector<double> result;
        if (!root) {
            return result;
        }
        q.push(root);
        while (!q.empty()) {
            int count = q.size();
            double sum = 0;
            for (int i = 0 ; i < count ; i++) {
                sum += q.front()->val;
                if (q.front()->left) {
                    q.push(q.front()->left);
                }
                if (q.front()->right) {
                    q.push(q.front()->right);
                }
                q.pop();
            }
            result.push_back(sum/count);
        }
        return result;
    }
};
  • 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

102. 二叉树的层次遍历(难度:中等)

  • 用队列queue实现,代码如下:
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root) {
            return vector<vector<int>>();
        }
        vector<vector<int>> result;
        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int count = q.size();//q.size()的值会变化
            for(int i = 0 ; i < count ; i++) {
                TreeNode* temp = q.front();
                res.push_back(temp->val);
                q.pop();
                if(temp->left != nullptr) {
                    q.push(temp->left);
                }
                if(temp->right != nullptr) {
                    q.push(temp->right);
                }
            }
            result.push_back(res);
            res.clear();
        }
        return result;
    }
};
  • 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

三、前中后序遍历

105. 从前序与中序遍历序列构造二叉树(难度:中等)

  • 用哈希表存储每个节点出现在中序遍历中的位置;
  • 前序遍历中的第一个点为mid,在哈希表中找到mid的位置,中序遍历中mid左边的值均为左子树,右边的值均为右子树;
  • 然后更新起始值、结束值、根节点值后,左右子树分别递归;
  • 代码如下:
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int , int> hash;
        if (preorder.empty()) {
            return nullptr;
        }
        for (int i = 0 ; i < preorder.size() ; i++) {
            hash[inorder[i]] = i;
        }
        return helper(preorder , hash , 0 , preorder.size() - 1 , 0);
    }

    TreeNode* helper(vector<int>& preorder , unordered_map<int , int>& hash , int s0 , int e0 , int s1) {
        if (s0 > e0) {
            return nullptr;
        }
        int mid = preorder[s1] , index = hash[mid] , leftLen = index - s0;
        TreeNode* node = new TreeNode(mid);
        node->left =  helper(preorder , hash , s0 , index - 1 , s1 + 1);
        node->right = helper(preorder , hash , index + 1 , e0 , s1 + leftLen + 1);
        return node;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

144. 二叉树的前序遍历(难度:中等)

  • 递归的本质是栈调用,使用栈来实现迭代;
  • 注意入栈顺序,由于栈先进后出,所以先入栈右节点,这样就可以先遍历到左节点,符合先序遍历的逻辑 ;
  • 代码如下:
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) {
            return result;
        }
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            result.push_back(node->val);
            if(node->right) {
                s.push(node->right);
            }
            if(node->left) {
                s.push(node->left);
            }
        }
        return result;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

四、二叉查找树

	左子树中所有节点的值小于父节点,右子树中所有节点的值大于父节点;
	对于一个二叉查找树,可以在O(nlogn)的时间内查找一个值是否存在:从根节点开始,若当前节点的值大于查找值,则向左下走,反之向右下走;
	二叉查找树是有序的,中序遍历的结果是排序好的数组。
  • 1
  • 2
  • 3

一个二叉查找树的实现代码如下:

template <class T>
class BST {
	struct Node {
		T data;
		Node* left;
		Node* right;
	};
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  1. 清空二叉查找树
	Node* makeEmpty(Node* t) {
		if (t == nullptr) {
			return nullptr;
		}
		makeEmpty(t->left);
		makeEmpty(t->right);
		delete t;
		return nullptr;
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  1. 构造二叉查找树
	Node* insert(Node* t , T x) {
		if (t == nullptr) {
			t = new Node;
			t->data = x;
			t->left = nullptr;
			t->right = nullptr;
		}
		else if (x > t->data) {
			t->right = insert(t->right , x);
		}
		else if (x < t->data) {
			t->left = insert(r->left , x);
		}
		return t;
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  1. 寻找二叉查找树元素
	Node* find(Node* t , T x) {
		if (t == nullptr) {
			return nullptr;
		}
		else if (x > t->data) {
			return find(t->right , x);
		}
		else if (x < t->data) {
			return find(t->left , x);
		}
		return t;
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  1. 寻找二叉查找树最小值
	Node* findMin(Node* t) {
		if (t == nullptr || t->left == nullptr) {
			return t;
		}
		return findMin(t->left);
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  1. 寻找二叉查找树最大值
	Node* findMax(Node* t) {
		if (t == nullptr || t->right == nullptr) {
			return t;
		}
		return findMin(t->right);
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  1. 指定元素删除
	Node* remove(Node* t , T x) {
		Node* temp;
		if (t == nullptr) {
			return nullptr;
		}	
		else if (x < t->data) {
			t->left = remove(t->left , x);
		}
		else if (x > t->data) {
			r->right = remove(t->right , x);
		}
		else if (t->left && t->right) {
			temp = findMin(t->right);
			t->data = temp->data;
			t->right = remove(t->right , t->data);
		}
		else {
			temp = t;
			if (t->left == nullptr) {
				t = t->tight;
			}
			else if (t->right == nullptr) {
				t = t->left;
			}
			delete temp;
		}
		return t;
	}
  • 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

99. 恢复二叉搜索树(难度:困难)(待进阶)

  • 思路清晰,但使用到的辅助空间较多;
  • 首先使用前序、中序遍历分别保存二叉树的数据;
  • 然后在中序遍历中找到位置错误的两个元素,并记录在check_result数组中;
  • 在前序遍历的数组中将位置错误的两个元素互换位置;
  • 清空原二叉树,只保留头节点,然后按照修改后的前序遍历的数组重新构造二叉树,这时构造好的二叉树即为所求;
  • (进阶难度需要使用到莫里斯遍历算法,容日后再更)
  • 代码如下:
class Solution {
public:
    void recoverTree(TreeNode* root) {
        vector<int> pre_result , ino_result , check_result;
        pre_result = preorder(root , pre_result);
        ino_result = inorder(root , ino_result);
        check_result = check(ino_result);
        for(int i = 0 ; i < pre_result.size() ; i++) {
            if (pre_result[i] == check_result[0]) {
                pre_result[i] = check_result[1];
            }
            else if (pre_result[i] == check_result[1]) {
                pre_result[i] = check_result[0];
            }
        }
        root = makeEmpty(root);
        //root = new TreeNode;
        root->val = pre_result[0];
        root->left = nullptr;
        root->right = nullptr;
        for (int i = 1 ; i < pre_result.size() ; i++) {
            root = insert(root , pre_result[i]);
        }
    }

    vector<int> preorder(TreeNode* root , vector<int>& pre_result) {
        if (root == nullptr) {
            return pre_result;
        }
        pre_result.push_back(root->val);
        preorder(root->left , pre_result);
        preorder(root->right , pre_result);
        return pre_result;
    }

    vector<int> inorder(TreeNode* root , vector<int>& ino_result) {
        if (root == nullptr) {
            return ino_result;
        }
        inorder(root->left , ino_result);
        ino_result.push_back(root->val);
        inorder(root->right , ino_result);
        return ino_result;
    }

    vector<int> check(vector<int> ino_result) {
        vector<int> check_result;
        int flag = 0 , temp = 0;
        for(int i = 0 ; i < ino_result.size() - 1 ; i++) {//-1防止数组越界
            if (flag == 0 && ino_result[i] > ino_result[i + 1]) {
                flag = 1;
                check_result.push_back(ino_result[i]);
                temp = ino_result[i + 1];
            }
            else if (flag == 1 && ino_result[i] > ino_result[i + 1]) {
                flag = -1;
                check_result.push_back(ino_result[i + 1]);
            }
        }
        if (flag == 1) {
            check_result.push_back(temp);
        }
        return check_result;
    }

    TreeNode* makeEmpty(TreeNode* root) {
        if(root->left != nullptr) {
            delete root->left;
        }
        if(root->right != nullptr) {
            delete root->right;
        }
        return root;
    }

    TreeNode* insert(TreeNode* root , int x) {
        if (root == nullptr) {
            root = new TreeNode;
            root->val = x;
            root->left = nullptr;
            root->right = nullptr;
        }
        if (x > root->val) {
            root->right = insert(root->right , x);
        }
        else if (x < root->val) {
            root->left = insert(root->left , x);
        }
        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
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91

669. 修剪二叉搜索树(难度:中等)

  • 代码如下:
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root) {
            return root;
        }
        if(root->val < low) {
            return trimBST(root->right , low , high);//右子树可能在范围内
        }
        if (root->val > high) {
            return trimBST(root->left , low , high);//左子树可能在范围内
        }
        root->left = trimBST(root->left , low , high);//检查并构造左子树
        root->right = trimBST(root->right , low , high);//检查并构造右子树
        return root;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

五、字典树

208.实现Tire(前缀树)(难度:中等)

  • 代码如下:

  • 1

226. 翻转二叉树(难度:简单)

  • 思路简单,代码如下:
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) {//处理空树
            return root;
        }
        swap(root->left , root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

617. 合并二叉树(难度:简单)

  • 思路简单,代码如下:

  • 1
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/727696
推荐阅读
相关标签
  

闽ICP备14008679号