Java教程

编程题分类——树

本文主要是介绍编程题分类——树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言

技巧

  1. 前序/后序+中序序列可以唯一确定一棵二叉树。递归建树。

正文

1. 按之字形顺序打印二叉树

code

答案
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* root) {
        vector<vector<int>> arr_out;
        vector<int> arr_small;
        if(root==nullptr)
            return arr_out;
        stack<TreeNode*> st1;
        stack<TreeNode*> st2;
        st1.push(root);
        while(!st1.empty()||!st2.empty())
        {
            while(!st1.empty())
            {
                TreeNode* temp1 = st1.top();
                arr_small.push_back(temp1->val);
                if(temp1->left)
                    st2.push(temp1->left);
                if(temp1->right)
                    st2.push(temp1->right);
                st1.pop();
            }
            if(arr_small.size())
            {
                arr_out.push_back(arr_small);
                arr_small.clear();
            }
                
            
            while(!st2.empty())
            {
                TreeNode* temp2 = st2.top();
                arr_small.push_back(temp2->val);
                if(temp2->right)
                    st1.push(temp2->right);
                if(temp2->left)
                    st1.push(temp2->left);
                st2.pop();
            }            
            if(arr_small.size())
            {
                arr_out.push_back(arr_small);
                arr_small.clear();
            }
            
        }
        return arr_out;
    }
    
};

2. 层序遍历二叉树

反正就是用队列。
code

答案
void layerTrace(BTreeNode *T)
{
	if(T== nullptr)//先判断这棵树是否为空
		return;
	BTreeNode *p=T;
	queue<BTreeNode*>q;
	q.push(p);//然后让头结点先入队列
	while(!q.empty())//这里可以去判断队列是否非空
	{
		p=q.front();//队列中的元素出来,
		q.pop();
		cout<<<<p->data;
		if(p->left!= nullptr)q.push(p->left);//找左子树,让其入队列
		if(p->right!= nullptr)q.push(p->right);//找,让其入队列右子树
	}
}

3. 完全二叉树怎么判断?

思路:转变思路,如何判断该树不是完全二叉树,就是层序遍历已经输出null节点了,后面却还有节点。
完全二叉树的性质:从根往下数,除了最下层外都是全满(都有两个子节点),而最下层所有叶结点都向左边靠拢填满。
code

答案
class Solution
{
public:
	bool isCompleteTree(TreeNode* root)
	{
		queue<TreeNode*> q;
		bool reachNull = false;
		q.push(root);
		while (!q.empty())
		{
			TreeNode* cur = q.front();
			q.pop();
			if (cur == nullptr)
			{
				reachNull = true;
				continue;
			}
			else
			{
				if (reachNull)
				{
					return false;
				}
				q.push(cur->left);
				q.push(cur->right);
			}
		}
		return true;
	}
};

3、 二叉树的序列化和反序列化

4. 二叉搜索树的第k个结点

题目
在这里插入图片描述
方法一:
code

答案
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* res;
    TreeNode* KthNode(TreeNode* root, int k) {
        inOrder(root,k);
        return res;
    }
    void inOrder(TreeNode* root,int& k)
    {
        //中序遍历,第k个节点即为所求的节点
        if(root==nullptr)
            return;
        if(root->left)
            inOrder(root->left,k);
        k--;//error1:要先进行减法
        if(k==0)
            res = root;
        if(root->right)
            inOrder(root->right,k);
    }
};

方法二:非递归的方式,维护一个栈。

答案
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* root, int k) {
        //中序遍历,非递归的话,需要维护一个栈
        stack<TreeNode*> st;
        TreeNode* res = NULL;//error3:要最终返回的元素,一般要记得进行初始化
        int n = 0;
        TreeNode* cur = root;
        while(!st.empty()||cur)
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            
            cur= st.top();//error1:注意当前栈顶元素要赋给cur
            n++;
            st.pop();
            if(n==k)
            {
                res = cur;
                return res;
            }
            cur = cur->right;//error2:直接把当前元素的右节点也放入栈即可
        }
        return res;
    }
};

5. 重建二叉树

题目
在这里插入图片描述
code

答案
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()==0||vin.size()==0)
            return nullptr;
        int rootVal = pre[0];
        int rootIndex = 0;
        TreeNode* root = new TreeNode(rootVal);
        for(int i = 0;i<vin.size();i++)
        {
            if(vin[i]==rootVal)
            {
                rootIndex = i;
                break;
            }
        }
        
        vector<int> pre_left;
        vector<int> vin_left;
        vector<int> pre_right;
        vector<int> vin_right;
        for(int j = 0;j<rootIndex;j++)
        {
            pre_left.push_back(pre[j+1]);
            vin_left.push_back(vin[j]);
        }
        
        for(int k = rootIndex+1;k<vin.size();k++)
        {
            pre_right.push_back(pre[k]);
            vin_right.push_back(vin[k]);
        }
        
        root->left = reConstructBinaryTree(pre_left,vin_left);
        root->right = reConstructBinaryTree(pre_right,vin_right);
        
        return root;
    }
};

6. 树的子结构

题目
在这里插入图片描述

code

答案
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr||root2==nullptr)
            return false;
        bool result;
        if(root1->val==root2->val)//如果当前的节点是相等的,就继续递归比较其他节点
        {
            result =  Hastree(root1,root2);
        }
       if(!result)
        {
            result = HasSubtree(root1->left,root2); //否则就拿左节点和子结构进行比较
        }
       if(!result)
        {
            result = HasSubtree(root1->right,root2);//否则就拿右节点和子结构进行比较
        }
        return result;
        
        
    }
    bool Hastree(TreeNode* root1,TreeNode* root2)
    {
        if(root2==NULL)
            return true;
        if(root1==NULL)
            return false;
        if(root1->val!=root2->val)
            return false;
        return Hastree(root1->left,root2->left)&&Hastree(root1->right,root2->right);
    }
};

7. 二叉树的镜像

题目
在这里插入图片描述

code

答案
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* root) {
        //类似于后序遍历
       if(root==nullptr)
           return nullptr;
        Mirror(root->left);
        Mirror(root->right);
        TreeNode* temp = root->left;
        root->left  = root->right;
        root->right = temp;
        
        return root;
    }
};

8. 二叉树的最近公共祖先

题目
在这里插入图片描述

9. 二叉树的遍历(前序,中序,后序,递归+迭代 )

9_1_1. 前序遍历(递归)

code

答案
class Solution {
public:
	 void traversal(TreeNode* cur, vector<int>& vec) {
		 if (cur == NULL) 
		 	return;
		 vec.push_back(cur->val); // 中
		 traversal(cur->left, vec); // 左
		 traversal(cur->right, vec); // 右
	 }
	 vector<int> preorderTraversal(TreeNode* root) {
		 vector<int> result;
		 traversal(root, result);
		 return result;
	 }
};

9_1_2.前序遍历(迭代)

code

答案
vector<int> preorder(TreeNode* root)
{
		vector<int> res;
		if(root==NULL)
			return res;
		stack<TreeNode*> st;
		st.push(root);
		while(!st.empty())
		{
				TreeNode* node = st.top();
				res.push(node);
				st.pop();
				if(node->right)
					st.push(node->right);
				if(node->left)
					st.push(node.left);
		}
		return result;
}

10. 二叉树的最近公共祖先

题目
在这里插入图片描述
code

答案
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //首先判断某节点是不是另一个节点子节点
        //看能不能把子结构的那道题目给套进来。
        if(root==nullptr||root==p||root==q)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(left!=nullptr&&right!=nullptr)
            return root;
        else if(left!=nullptr)
            return left;
        else if(right!=nullptr)
            return right;
        return nullptr;
    }
};

这道题目应该就是普通的递归,其实跟回溯应该没什么关系了,可能一讲到二叉树,大部分的思路应该都要是递归的思路会比较对。

11. 二叉搜索树中的插入操作

题目
在这里插入图片描述

解题思路

此题的解题核心,还是说要找到合适的位置,去插入这个节点。
那么插入有两种方式,
第一:按照普通的插入方式,让parent节点指向当前要插入的这个位置。我当时也是觉得这个位置很难找。
第二:采用递归的方式,找到合适的位置,返回这个插入的节点就可以了。

代码

方法一

答案
/**
 * Definition for a binary tree node.
 * 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* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr)
        {
            root = new TreeNode(val);
            return root;
        }
        if(val>root->val)
        {
            root->right = insertIntoBST(root->right,val);
        }
        else
        {
            root->left = insertIntoBST(root->left,val);
        }
        return root;

    }
};

方法二
code

答案
/**
 * Definition for a binary tree node.
 * 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* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr)
        {
            root = new TreeNode(val);
            return root;
        }
        TreeNode* parent = nullptr;
        bst(root,val,parent);
        return root;
    }
    void bst(TreeNode* cur,int val,TreeNode* parent)
    {
        if(cur==nullptr)
        {
            TreeNode* node = new TreeNode(val);
            if(val>parent->val)
                parent->right = node;
            else
                parent->left = node;
            return;
        }
        parent = cur;
        if(parent->val>val)
            bst(cur->left,val,parent);
        else
            bst(cur->right,val,parent);
    }
};

12. 二叉树的最大深度

二叉树的最大深度
在这里插入图片描述
方法一:递归
code

答案
/**
 * Definition for a binary tree node.
 * 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:
    int maxDepth(TreeNode* root) {
        if(root==nullptr)
            return 0;
        int left = maxDepth(root->left);//计算左节点
        int right = maxDepth(root->right);//计算右子树
        return max(left,right)+1;
    }
};

方法二:迭代
code

答案
/**
 * Definition for a binary tree node.
 * 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:
    int maxDepth(TreeNode* root) {
        //13:52->
        //弄一个队列来保存这些数值
        if(root==nullptr)
            return 0;
        queue<TreeNode*> q;
        q.push(root);
        int count=0;
        while(!q.empty())
        {
            int size = q.size();
            for(int i = 0;i<size;i++)
            {
                TreeNode* node = q.front();//取出元素
                q.pop();
                if(node->left)//加入其孩子节点
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            count++;
        }
        return count;

    }
};

方法三:前序遍历 回溯——从上往下找
code

答案
/**
 * Definition for a binary tree node.
 * 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:
    int result = 0;
    int maxDepth(TreeNode* root) {
        if(root==nullptr)
            return 0;
        getDepth(root,1);
        return result;
    }
    void getDepth(TreeNode* node,int depth)
    {
        if(result<depth)
            result = depth;
        if(node->left==nullptr&&node->right==nullptr)
            return;
        if(node->left) 
        {
            depth++;
            getDepth(node->left,depth);
            depth--;
        }
        if(node->right)
        {
            depth++;
            getDepth(node->right,depth);
            depth--;
        }
        return;
    }
};

13. 左叶子之和

题目
在这里插入图片描述
方法1:迭代 code

答案
/**
 * Definition for a binary tree node.
 * 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:
    int sumOfLeftLeaves(TreeNode* root) {
        //递归不会用迭代的方式
        if(root==nullptr)
            return 0;
        queue<TreeNode*> q;
        q.push(root);
        int sum = 0;
        while(!q.empty())
        {
            int size = q.size();
            for(int i = 0;i<size;i++)
            {
                TreeNode* node = q.front();
                if(node->left)
                {
                    if(node->left->left==nullptr&&node->left->right==nullptr)//error1:疏忽了左叶子节点的定义
                        sum+=node->left->val;
                    q.push(node->left);
                }
                if(node->right)
                {
                    q.push(node->right);
                }
                q.pop();
            }
        }
        return sum;
    }
};

方法二:递归法
code

答案
/**
 * Definition for a binary tree node.
 * 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:
    int sum = 0;
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==nullptr)
            return 0;
        int left = sumOfLeftLeaves(root->left);
        int right = sumOfLeftLeaves(root->right);
        if(root->left)
        {
            if(root->left->left==nullptr&&root->left->right==nullptr)
                sum+=root->left->val;
        }
        return sum;

    }
    
};

参考

  1. 剑指Offer
  2. Leetcode 100题
这篇关于编程题分类——树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!