算法提高：二叉树算法题目大全

二叉树的非递归遍历（前序）

思路

优先判断树是否为空，空树不遍历。
准备辅助栈，首先记录根节点。
每次从栈中弹出一个元素，进行visit访问，然后验证该节点的左右子节点是否存在，存的话的加入栈中，优先加入右节点。

代码

void preorderNoRecursion(btNode* p)
{
 if (p != NULL)
 {
  int top = -1;
  btNode* stack[50];
  btNode* temp;
  stack[++top] = p;
  while (top != -1)
  {
   temp = stack[top--];
   std::cout << temp->data << ' '; //viist
   if (temp->rc != NULL)
    stack[++top] = temp->rc;//push right child
   if (temp->lc != NULL)
    stack[++top] = temp->lc;//push  left child
  }
 }
}

二叉树的非递归遍历（中序）

思路

从头节点开始一直向左next，然后路上所有的node push到stack
左next为NULL时，stack pop 一个node，visit 这个node
判断node 是否有right child ，如果有当前节点设置为右孩子，继续重复1，2
如果没有右孩子，再从栈中pop 一个重复3
stack 为空时结束

代码

void Inorder_I(BiTree T)//中序的非递归遍历
{
    
    stack<BiTNode*>s;
    BiTree p=T;
    while(p!=NULL||!s.empty())//栈不空或P不空时循环
    {
        if(p)                 //一路向左
        {
            s.push(p);       //当前节点入栈
            p=p->lchild;     //左孩子不空，一直往左走
        }
       else                      //出栈，并转向出栈节点的右子树
        {
            p=s.top();             
            cout<<p->data;        
            s.pop();          //栈顶元素出栈，访问出栈节点
            p=p->rchild;      //返回while循环继续进入if-else语句
        }
    }
 
}

二叉树的非递归遍历（后序）

思路

先序遍历顺序的根-左-右改为根-右-左

用这个栈把结果存起来，然后输出，就是后序遍历

代码

void postorderNoRecursion(btNode* p)
{
	if (p != NULL)
	{
		btNode* stack1[50];//栈1为辅助栈
		btNode* stack2[50];//栈2为访问栈
		int top1 = -1, top2 = -1;
		btNode* temp;
		stack1[++top1] = p;
		while (top1 != -1)//修改先序非递归遍历进行交换
		{
			temp = stack1[top1--];
			stack2[++top2] = temp;
			if (temp->lc != NULL)
				stack1[++top1] = temp->lc;//先入左孩子结点
			if (temp->rc != NULL)
				stack1[++top1] = temp->rc;//后入右孩子结点
		}
		while (top2 != -1)//再逆序
			std::cout << stack2[top2--]->data << ' ';//访问栈2中的数据
	}
}

二叉树的层序遍历

思路

使用队列，从头节点开始，加入队列，加入队列时visit
弹出队头，遍历左右孩子，并visit，然后把左右孩子加入队列
重复2.3，遇到NULL孩子不加入队列，不打印
直到队列为NULL

代码

class Solution {	//二叉树的层次遍历
public:
	vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> result;
		queue<TreeNode*> que;
		if (root != nullptr){
			que.push(root);
		}
		while (!que.empty()) {
			vector<int> temp;
			int length = que.size();
			for (int i = 0; i < length; ++i) {
				TreeNode* tempNode = que.front();
				que.pop();
				temp.push_back(tempNode->val);
				if (tempNode->left) {
					que.push(tempNode->left);
				}
				if (tempNode->right) {
					que.push(tempNode->right);
				}
			}
			result.push_back(temp);
		}
		return result;
	}
};

求二叉树的最大宽度

思路

层序遍历的变体，用一个map做记录，把每一个node 的层数作为key，value就是遍历一个+1

遍历完树就可以拿到所有层的宽度

也可以不使用map，多使用一个队列，一层使用一个队列，当一个队列为NULL时，另外一个队列达到最大值，记录一下这个层的number，一样可以做到上面的效果。

代码

int function(Node* head) {
	if (head == NULL)
		return 0;
	unordered_map<Node*, int> m;//装每个结点以及对应的第几层
	queue<Node*> q;//宽度优先遍历
	q.push(head);//先将头装进去
	int max_w = 0;//记录最大宽度
	int h = 0;//第几层
	int floor[100] = { 0 };//每一层的结点个数
	m.insert(make_pair(head, h));
	while (!q.empty()) {
		
		//取出元素
		Node* cur = q.front();//头拿出来
		q.pop();//弹出去
 
		//给压入的元素标号
		h = m[cur];
		if (cur->left != NULL) {
			q.push(cur->left);
			m.insert(make_pair(cur->left, h + 1));
		}
		if (cur->right != NULL) {
			q.push(cur->right);
			m.insert(make_pair(cur->right, h + 1));
		}
		floor[h]++;
	}
	//寻找每一层的最大结点数
	for (int i = 0;i <= h-1;i++)
		max_w = max_w < floor[i] ? floor[i] : max_w;
	return max_w;
}

二叉树的序列化与反序列化（前序方式）

思路

序列化和反序列化出了中序存在歧义，其他的方式都可以转（后序可以转为变体前序）。

反序列化的过程和序列化的过程也非常相似，核心就是占位符#。

非递归的前序反序列化主要是：

创建根节点，并入栈
不断反序列化，设置为node的左孩子，并入栈，直到遇到#
然后出栈一个node，序列化字符串的下一个元素若不为#，就设置为node的右孩子，继续2
若为#，继续出栈node重复3
直到序列化字符串结束

代码

//序列化函数
void serialization(btree* head, queue<int>* que) {	//前序遍历入队--(递归法)
	if (!head) {	//节点为空则返回 NULL 并 return
		que->push(NULL);
		return;
	}

	que->push(head->data);	//入队
	serialization(head->left, que);	//左子树入队
	serialization(head->right, que);	//右子树入队
}

//反序列化函数 - 递归版本
btree* bulidTree(queue<int>* que) {	//按前序遍历入队的顺序依次出队, 建树
	int num = que->front();	//获取队头元素
	que->pop();	//出队
	if (!num) {	//若为空则返回 NULL
		return NULL;
	}
	btree* head = new btree;	//非空则建立节点
	head->data = num;	//对节点赋值

	head->left = bulidTree(que);	//建立节点的左子树
	head->right = bulidTree(que);	//建立节点的右子树
	return head;	//返回节点
}

二叉树的序列化与反序列化（层序方式）

思路

层序方式的序列化和反序列化的核心在于标志空节点的占位符，比如#

序列化的时候需要NULL孩子，序列化为#

反序列化的时候，也是遍历的过程：

先把根创建出来，然后加入一个队列中
出队一个节点，然后从序列化字符中取两个值（可能有#）
如果是#就不管，如果不是#号，第一个值为左孩子，第二个值为右孩子，创建出来并入队
重复2，3，直到所有序列化字符

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
 
    /*
    解题思路：
    1.序列比：将所有节点的val（包括空节点）按照层次遍历存储到string，空节点存入null，用逗号','隔开
    2.反序列化：将string每个元素分解成stringArr存储每个元素，然后遍历
    */
    // Encodes a tree to a single string.
    string serialize(TreeNode* root)
    {
        if (root == nullptr)
            return "#";
        string result;
        std::queue<TreeNode*> nodeQueue;
        TreeNode* cur = nullptr;
        int isValid = false;
        int size = 0;
        nodeQueue.push(root);
        while (!nodeQueue.empty()) // 正常的层次遍历
        {
            size = nodeQueue.size();
            for (int i = 0; i < size; ++i)
            {
                cur = nodeQueue.front();
                nodeQueue.pop();
                if (cur == nullptr) // 这里有区别，如果是空节点则存储为'#'
                {
                    result.append("#,");
                    continue;
                }
                result.append(std::to_string(cur->val) + ","); // 存储节点信息
                nodeQueue.push(cur->left); //这里有区别，不管是否空节点都压入栈
                nodeQueue.push(cur->right); //这里有区别，不管是否空节点都压入栈
            }
        }
        return result;
    }
 
    void toStrArr(const string& data, vector<string>& valsStr)
    {
        string valStr;
        valStr.reserve(10); // 优化，预分配10个byte
        for (const char& ch : data)
        {
            if (ch == ',')
            {
                valsStr.push_back(valStr); // 将每个节点的值存入数组
                valStr.clear(); // 初始化
            }
            else
            {
                valStr.push_back(ch); // 存储每个节点的值
            }
        }
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.compare("#") == 0) // 如果整个字符串为空，则直接返回nullptr
            return nullptr;
        vector<string> valsStr; // 数组字符串存储每个节点信息
        toStrArr(data, valsStr); // 将string转为数组字符串
        int size = valsStr.size();
        TreeNode* root = new TreeNode(std::stod(valsStr[0]));
        TreeNode* parent = nullptr;
        std::queue<TreeNode*> nodeQueue;
        nodeQueue.push(root); // 将根节点压入栈
 
        for (int i = 1; i < size; ++i)
        {
            parent = nodeQueue.front();
            nodeQueue.pop();
            if (valsStr[i].compare("#"))
            {
                parent->left = new TreeNode(std::stod(valsStr[i])); // 创建该节点左子节点
                nodeQueue.push(parent->left); // 非空则压入栈，顺序访问每个节点
            }
            if (valsStr[++i].compare("#"))
            {
                parent->right = new TreeNode(std::stod(valsStr[i])); // 创建该节点右子节点
                nodeQueue.push(parent->right); // 非空则压入栈，顺序访问每个节点
            }
        }
        return root; // 返回原始二叉树
    }
};
 
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

二叉树找到两个节点的最近公共祖先

题目

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足1≤n≤10^5, 节点值val满足区间 [0,n)

要求：时间复杂度O(n)

注：本题保证二叉树中每个节点的val值均不相同。

思路

这个题目是一个典型的树型动态规划，二叉树绝大多数的难题都是动态规划，比如说判断最大的线索二叉树（LeetCode——654），比如找到树上最远距离，本质上都是动态规划

按照动态规划的思路，就是把一个很大规模的问题，变成一个一个的小规模相同类型的问题，然后把结果进行逻辑处理，步步上传。

这个题目中找最近的公共祖先按照动态规划的思维去拆分就是：

先在左、右子树中找看是否存在最近祖先，是否存在A、是否存在B；
然后一直遍历左右子树，直到按照后序遍历的方式把整个树遍历完；
遍历的过程中如果某个子树存在最近祖先，就把这个节点带上；
最后遍历完就得到了最终的最近祖先了；

代码

#include <iostream>
#include <string>
using namespace std;

class Tree {
public :
    char value;
    Tree* r;
    Tree* l;
};


class Res {
public:
    char ans_; // 最近的公共祖先
    bool isA_;
    bool isB_;
    Res(char ans, bool isA, bool isB):ans_(ans),isA_(isA),isB_(isB){}
    Res(){}
};

char A = 'A';
char B = 'B';
class solution {
public:
    void function(Tree*root) {
        if(!root) {
            //TODO: return nullptr
            cout <<"there is not ancestor" <<endl;
            return ;
        }
        Res res = prcess(root);
        if (res.ans_ != '') {
            cout << "nearst ancestor is " <<res.ans_ <<endl;
        }
    }

private:
    Res process(Tree*node) {
        if(!node) {
            return Res('',false,false);
        }
        Res res;
        res.ans_ = '';
        res.isA_ = false;
        res.isB_ = false;
        Res rl = process(node->l);
        Res rr = process(node->r);
        if (rl.ans_ != '') {
            res.ans_ = rl.ans_;
            res.isA_ = rl.isA_;
            res.isB_ = rl.isB_;
        }

        else if (rr.ans_ != '') {
            res.ans_ = rr.ans_;
            res.isA_ = rr.isA_;
            res.isB_ = rr.isB_;
        }

        else if (rl.isA_ || rr.isA_ || node->value == A) {
            res.isA_;
        }

        else (rl.isB_ || rr.isB_ || node->value == B) {
            res.isB_;
        }

        if(res.isA_ && res.isB_) {
            res.ans_ = node->value;
        }
      

        return res;
    }
};

原文链接：https://blog.csdn.net/qq_32378713/article/details/127421483

你可能也喜欢