当前位置博文首页 > soul-chang 的博客：算法与数据结构学习1-树

soul-chang 的博客：算法与数据结构学习1-树

作者：[db:作者] 时间：2021-09-20 22:56

树

最小深度
先判断左右子树是否存在为空的情况，如果某一边为空，则返回另一边的深度(因为此时并没有到达叶节点，所以需要继续下去)；否则的话，使用递归方法求最小深度。->最大深度则很简单，直接递归求最大就好。

class Solution {
public:
    int run(TreeNode *root) {
        vector<int> res;
        if(root == nullptr)
            return 0;
        if(root->left == nullptr || root->right == nullptr)
            return max(run(root->left), run(root->right)) + 1;
        return min(run(root->left), run(root->right)) + 1;
    }
};

前序遍历、中序遍历和后序遍历的非递归解法
一般迭代方法的话会使用一个栈来辅助，下面给出一套实例：

//中序遍历
class Solution{
public:
	vector<int> inorderTraversal(TreeNode* root){
		vector<int> vec;
		if(root == nullptr) return vec;
		stack<TreeNode*> stk;
		TreeNode* curr = root;
		while(curr != nullptr || !stk.empty()){
			while(curr != nullptr){
				stk.push(curr);
				curr = curr->left;
		}
		curr = stk.top();
		stk.pop();
		vec.push_back(curr->val);
		curr = curr->right;
	}
	return vec;
};

//前序遍历
class Solution{
public:
	vector<int> preorderTraversal(TreeNode* root){
		vector<int> vec;
		if(root == nullptr) return vec;
		stack<TreeNode*> stk;
		stk.push(root);
		while(!stk.empty()){
			TreeNode* curr = stk.top();
			stk.pop();
			vec.push_back(curr->val);
			if(curr->right != nullptr)
				stk.push(curr->right);
			if(curr->left != nullptr)
				stk.push(curr->left);
		}
		return vec;
	}
};

//后序遍历
class Solution{
public:
	vector<int> postorderTraversal(TreeNode* root){
		vector<int> vec;
		if(root == nullptr) return vec;
		stack<TreeNode*> stk;
		stk.push(root);
		while(!stk.empty()){
			TreeNode* curr = stk.top();
			stk.pop();
			vec.insert(vec.begin(), curr->val);
			if(curr->left != nullptr)
				stk.push(curr->left);
			if(curr->right != nullptr)
				stk.push(curr->right);
		}
		return vec;
	}
};

求根到叶节点连接起来后的和
例如：

[1,2,3]这棵树
The root-to-leaf path 1->2 表示数字12
The root-to-leaf path 1->3 表示数字13
返回值　sum = 12 + 13 = 25

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        return sumNumbersCore(root, 0);
    }
private:
    int sumNumbersCore(TreeNode *root, int s){
        if(root == NULL)
            return 0;
        if(root->left == NULL && root->right == NULL)
            return s = s*10 + root->val;
        return sumNumbersCore(root->left, s * 10 + root->val) + sumNumbersCore(root->right, s*10 + root->val);
    }
};

使用递归方式求解，如果一个节点有左子节点，那么用这个节点乘10加上左节点的值；右节点亦是如此，递归就可以求得答案。

二叉树最大路径的和
例如：

[1,2,3,4,5]这棵树，最大路径的和为
sum = 5 + 2 + 1 + 3 = 11

同样使用递归方法，这个题可以注意到包括两种情况，第一种是左右子树各自路径最大加上根节点的值，另一种就是最大路径存在于左子树或右子树，即不需要添加根节点，参考代码为：

class Solution {
public:
    int maxValue;
    int maxPathSum(TreeNode *root) {
        maxValue = INT_MIN;
        maxSum(root);
        return maxValue;
    }
    int maxSum(TreeNode *root){
        if(root == nullptr)
            return 0;
        int left = max(0, maxSum(root->left));
        int right = max(0, maxSum(root->right));
        maxValue = max(maxValue, left + right + root->val);
        return max(left,right) + root->val;
        //最后两行代码理解：maxValue是记录当前根是否是最终根的值，因此我们使用left + right + root->val
        //但是对于上层（在return语句之后），我们不能同时选择左右两个，因此我们需要选择较大的一个
        //所以我们使用max（left，right）+ root->val来修剪下层分枝
    }
};

为树的每个节点添加右指针
此时树的结构为：

struct TreeLinkNode{
	TreeLinkNode *left;
	TreeLinkNode *right;
	TreeLinkNode *next;
}

如果某个节点不存在右节点，那么将这个节点的下一个节点设为NULL，初始时所有节点的下一个节点都为NULL。假设这是一个完全二叉树，且求解时只能使用常数的extra space.
解这道题时首先考虑到的是每个节点如果有子节点的话，先让它的左子节点指向右子节点，然后如果这个节点存在next节点，那么它的右子节点next指向这个节点next节点的左子节点，最后如果一个节点不存在子节点且不存在next节点，让它的next节点指向NULL，递归左右节点最终得到结果，示例代码如下

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL)
            return;
        TreeLinkNode* p = root;
        
        if(p->right){
            p->left->next = p->right;
            if(p->next)
                p->right->next = p->next->left;
        }else if(p->right == NULL && !p->next)
            p->next = NULL;
        connect(p->left);
        connect(p->right);
    }
};

进一步扩展，如果这棵树不是完全二叉树，而是一棵普通的树，那么如何书写代码？
此时问题变得非常复杂，欣赏一段代码：

class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode* head = root;//head表示的是某一层最左面的节点
        TreeLinkNode* prev = NULL;//pre用来表示下一层节点的移动
        TreeLinkNode* curr = NULL;//用curr表示某一层节点移动，curr=NULL表示某一层移动结束，开始下一层
        while(head != NULL){
            curr = head;
            prev = NULL;
            head = NULL;
            while(curr != NULL){
                if(curr->left != NULL){
                    if(prev != NULL)
                        prev->next = curr->left;
                    else
                        head = curr->left;
                    prev = curr->left;
                }
                if(curr->right != NULL){
                    if(prev != NULL)
                        prev->next = curr->right;
                    else
                        head = curr->right;
                    prev = curr->right;
                }
                curr = curr->next;
            }
        }
    }
};

路径和
给定一棵二叉树和一个和sum，判定是否存在一条从根到叶的路径使得路径上所有节点的和跟给定的和sum相等。一个简单的思路是将原问题递归表示为左右子树是否存在和为sum - root->val的子树，代码如下:

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if(root == nullptr)
            return false;
        if(root->left == nullptr && root->right == nullptr && root->val == sum)
            return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

原问题进一步延伸，给定一棵二叉树和一个和sum，找出所有从根到叶的路径使得路径上所有节点的和跟给定的和sum相等，返回一个二维向量。跟刚刚的思路类似，只不过将那些路径表示出来，代码如下：

class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> > paths;
        vector<int> path;
        findPaths(root, sum, path, paths);
        return paths;
    }
private:
    void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths){
        if(!node) return;
        path.push_back(node->val);
        if(!(node->left) && !(node->right) && sum == node->val)
            paths.push_back(path);
        findPaths(node->left, sum - node->val, path, paths);
        findPaths(node->right, sum - node->val, path, paths);
        path.pop_back();
    }
};

判断一棵二叉树是否为平衡二叉树
首先要了解基本概念，平衡二叉树就是每个节点的子树的深度的差不能超过１。
思路：基于DFS，我们不是为每个子节点显式调用depth（），而是在DFS递归中返回当前节点的高度。当当前节点的子树平衡时，函数dfsHeight（）返回非负值作为高度。否则返回-1。根据两个子树的的leftHeight和rightHeight，父节点可以检查子树是否是平衡的，并决定其return值。

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        if(root == NULL || (root->left == NULL && root->right == NULL))
            return true;
        return dfsHeight(root) != -1;
    }
private:
    int dfsHeight(TreeNode* root){
        if(root == NULL) return 0;
        int leftHeight = dfsHeight(root->left);
        if(leftHeight == -1) return -1;
        int rightHeight = dfsHeight(root->right);
        if(rightHeight == -1) return -1;
        
        if(abs(leftHeight - rightHeight) > 1) return -1;
        return max(leftHeight, rightHeight) + 1;
    }
};

二叉树层序遍历
给定一棵二叉树，返回节点值的层序遍历结果，比如

[3,9,20,#,#,15,7]
返回结果为
[ [3],
[9, 20],
[15, 7] ]

关于层序输出结果的题目有个经典套路，不同于使用栈的方法，用一个表示层数的参数level来先构造一个size为level的二维向量，然后将相同层数的节点不断加入向量中，本例代码如下:

class Solution {
public:
    vector<vector<int> > res;
    vector<vector<int> > levelOrder(TreeNode *root) {
        levelOrderCore(root, 0);
        return res;
    }
private:
    void levelOrderCore(TreeNode* root, int level){
        if(root == nullptr) return;
        if(level == res.size()){
            res.push_back(vector<int>());
        }
        res[level].push_back(root->val);
        levelOrderCore(root->left, level + 1);
        levelOrderCore(root->right, level + 1);
    }
};

扩展题目为从下向上返回向量，此时只需将结果反置一下即可

class Solution {
public:
    vector<vector<int> > res;
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        levelMaker(root,0);
        return vector<vector<int> > (res.rbegin(), res.rend());
    }
    void levelMaker(TreeNode *root, int level){
        if(root == NULL) return;
        if(level == res.size()){
            res.push_back(vector<int>());//create a new level
        }
        res[level].push_back(root->val);
        levelMaker(root->left, level + 1);
        levelMaker(root->right, level + 1);
    }
};

另一个扩展题目为返回一个zigzag的层序遍历结果，比如：

[3,9,20,#,#,15,7]
返回结果为
[ [3],
[20, 9],
[15, 7] ]

class Solution {
public:
    vector<vector<int> > res;
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        zigzag(root, 0);
        return res;
    }
private:
    void zigzag(TreeNode *root, int level){
        if(root == nullptr)
            return;
        if(level == res.size()){
            res.push_back(vector<int>());
        }
        if(level % 2 == 0)
            res[level].push_back(root->val);
        else
            res[level].insert(res[level].begin(), root->val);
        zigzag(root->left, level + 1);
        zigzag(root->right, level + 1);
    }
};

使用中序遍历和后序遍历构造二叉树
这道题目思路点是，后序遍历最后一个是根节点，然后从中序遍历中找到对应的节点，划分为左右两部分，递归求解。相对复杂一些，仔细消化。

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        return create(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
private:
    TreeNode* create(vector<int> &inorder, vector<int> &postorder, int i_start, int i_end, int p_start, int p_end){
        if(p_start > p_end)
            return nullptr;
        TreeNode* node = new TreeNode(postorder[p_end]);
        int pos;
        //查找中序遍历中根节点的位置
        for(int i = i_start; i <= i_end; i++){
            if(inorder[i] == node->val){
                pos = i;
                break;
            }
        }
        node->left = create(inorder, postorder, i_start, pos - 1, p_start, p_start + pos - i_start - 1);
        node->right = create(inorder, postorder, pos + 1, i_end, p_end - i_end + pos, p_end - 1);
        return node;
    }
};

扩展的用前序遍历和中序遍历构造二叉树跟这个类似

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return create(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
private:
    TreeNode *create(vector<int> &preorder, vector<int> &inorder, int p_start, int p_end, int i_start, int i_end){
    if(p_start > p_end)
        return nullptr;
    TreeNode* node = new TreeNode(preorder[p_start]);
    int tmp = 0;
    for(int i = i_start; i <= i_end; i++){
        if(inorder[i] == node->val){
            tmp = i;
            break;
        }
    }
    node->left = create(preorder, inorder, p_start + 1, p_start + tmp - i_start, i_start, tmp - 1);
    node->right = create(preorder, inorder, p_end - i_end + tmp + 1, p_end, tmp + 1, i_end);
    return node;
    }
};

对称树
题目：给定一棵二叉树，检查其是否是一棵对称树，即它跟自己镜像对称（以他的中间根节点为所在竖直方向为对称轴）。
初始想法是先左右中得出一个向量，再右左中得出一个向量，判断是否相等，但是类似[1,2,#]就会出错，所以这种暴力方法亦不能奏效。
这种类型题，直接提取左右节点建立函数，也用对称思路来解题，会省去许多不必要的思考细节

class Solution {
public:
    queue<int> q;
    bool isSymmetric(TreeNode *root) {
        if(root == nullptr)
            return true;
        return isSym(root->left, root->right);
    }
    bool isSym(TreeNode* left, TreeNode* right){
        if(left == nullptr || right == nullptr){
            return left == right;
        }
        if(left->val != right->val)
            return false;
        return (isSym(left->left, right->right) && isSym(left->right,right->left));
    }
};

相等树
判断两棵树是否相同，思路很简单，直接递归判断左右子树

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(p == nullptr || q == nullptr)
            return p == q;
        if(p->val != q->val)
            return false;
        return (isSameTree(p->left, q->left)&& isSameTree(p->right, q->right));
    }
};

搜索二叉树
判断一棵树是否为搜索二叉树，遇到搜索二叉树，首先想到中序遍历，然后用中序遍历辅助得到解题思路。

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if(root == nullptr)
            return true;
        stack<TreeNode*> stk;
        TreeNode* pre = nullptr;
        while(root != nullptr || !stk.empty()){
            while(root != nullptr){
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if(pre != nullptr && root->val <= pre->val) return false;
            pre = root;
            root = root->right;
        }
        return true;
    }
};

扩展，找出搜索二叉树第k个最小的元素

class Solution {
public:
    int kthSmallest(TreeNode *root, int k) {
        if(root == nullptr)
            return true;
        stack<TreeNode*> stk;
        while(root != nullptr || !stk.empty()){
            while(root != nullptr){
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if(--k == 0) break;
            root = root->right;
        }
        return root->val;
    }
};

unique binary search tree
给定一个数值n，判断有多少结构上唯一的BST（二叉搜索树）存储值1 … n。
使用动态规划的方法，这道题需要一定的数学推导辅助结题，假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数，即有:G(n) = f(1) + f(2) + f(3) + f(4) + … + f(n)
当i为根节点时，其左子树节点个数为[1,2,3,…,i-1]，右子树节点个数为[i+1,i+2,…n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),
上面两式可得:G(n) = G(0)G(n-1)+G(1)(n-2)+…+G(n-1)*G(0)

class Solution {
public:
    int numTrees(int n) {
        int G[n+1];
        memset(G,0,sizeof(int) * (n+1));
        G[0] = G[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                G[i] += G[j-1]*G[i-j];
            }
        }
        return G[n];
    }
};

题目扩展，将所有的结果输出出来，这时可以使用分治的方法，代码有点绕，要仔细理解领会，也是不断交换根节点，最终将所有情况都表示出来

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        return genTrees(1, n);
    }
    vector<TreeNode*> genTrees(int start, int end){
        vector<TreeNode*> vec;
        if(start > end){
            vec.push_back(nullptr);
            return vec;
        }
        if(start == end){
            vec.push_back(new TreeNode(start));
            return vec;
        }
        
        vector<TreeNode*> left, right;
        for(int i = start; i <= end; i++){
            left = genTrees(start, i - 1);
            right = genTrees(i + 1, end);
            //下面的代码是理解的关键,可以n=3举例，方便理解
            for(TreeNode* lnode: left){
                for(TreeNode* rnode: right){
                    TreeNode* root = new TreeNode(i);
                    root->left = lnode;
                    root->right = rnode;
                    vec.push_back(root);
                }
            }
        }
        return vec;
    }
};

总结

从上面的题目可以看到，由于树的特殊结构，递归方法是首选，然后要着重了解几种遍历的非递归解法，尤其中序遍历跟搜索二叉树关系密切，仔细观察12题的判断搜索二叉树方法。

上一篇：dennis_jiang的博客：速度提高几百倍，记一次数据结构在实际工作

下一篇：没有了

立即下载 - IIS7 站长工具包

soul-chang 的博客：算法与数据结构学习1-树

作者：[db:作者] 时间：2021-09-20 22:56

树

总结

最新 更多<<

推荐 更多<<

soul-chang 的博客：算法与数据结构学习1-树

作者：[db:作者] 时间：2021-09-20 22:56

树

总结

最新 更多<<

推荐 更多<<

最新更多<<

推荐更多<<