【面试HOT200】二叉树——深度优先搜索篇

本文主要是介绍【面试HOT200】二叉树——深度优先搜索篇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

系列综述：
💞目的：本系列是个人整理为了秋招面试的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于【CodeTopHot200】进行的，每个知识点的修正和深入主要参考各平台大佬的文章，其中也可能含有少量的个人实验自证，所有代码均优先参考最佳性能。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🌈【C++】秋招&实习面经汇总篇

文章目录

- 基础知识
- - 二叉树DFS基本算法
  - - 递归算法
    - 非递归算法
  - 相关题目
  - - 236. 二叉树的最近公共祖先
    - 110. 判断平衡二叉树（后序遍历的示例）
    - 222. 求树中结点的数量
    - 226. 翻转二叉树
    - 101. 对称二叉树
    - 左叶子之和
    - 二叉树的所有路径（带缓存的前序遍历）
    - 符合总和的路径
- 参考博客

😊点此到文末惊喜↩︎

基础知识

二叉树DFS基本算法

递归算法

注意

左右子树不需要if (root->left/rihgt)，因为递归出口已经判断了
后序遍历有个好处：可以先收集和处理孩子，然后根节点再进行处理

// 前序遍历
void Traversal(TreeNode *root) {if (root == nullptr) return ;Doing(root->val);       // 中Traversal(root->left);  // 左Traversal(root->right); // 右
}
// 中序遍历
void Traversal(TreeNode *root) {if (root == nullptr) return ;Traversal(root->left);  // 左Doing(root->val);       // 中Traversal(root->right); // 右
}
// 后序遍历
void Traversal(TreeNode *root, vector<int> vec) {if (root == nullptr) return ;Traversal(root->left);  // 左Traversal(root->right); // 右vec.emplace_back(root->val);// 中
}

非递归算法

注意点

vector<int> preorderTraversal(TreeNode* root) {vector<int> res;		// 结果容器stack<TreeNode*> st;	// 深度栈if(root != nullptr) st.push(root);	// 根非空则入栈// 遍历源容器while (!st.empty()) {	// key:注意使用的全部结点都是node// 先记录TreeNode *node = st.top();st.pop();// 后操作if (node != nullptr) {// 压入允许为逆序，注意根节点要后压入nullptrif (node->right) st.push(node->right);	if (node->left) st.push(node->left);	st.push(node);st.push(nullptr);} else {// 先记录node = st.top();st.pop();// 后操作res.emplace_back(node->val);}}return res;
}

相关题目

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

题目
- 给定一个二叉树, 找到该树中两个指定节点p和q的最近公共祖先。
复杂度分析：
- 时间复杂度 O(N)：其中 N为二叉树节点数；最差情况下，需要递归遍历树的所有节点。
- 空间复杂度 O(N)：最差情况下，递归深度达到 N
思路
- 递归出口：如果不是nullptr表示找到了
- 后序遍历：优先遍历左右子树并进行记录
- 结点处理
  - 如果左右子树都非空，一定表示该结点为公共祖先结点
  - 如果有一个为空，则向上传递非空的那个结点

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 递归出口：返回标志，不为空说明是祖先结点if (root == p || root == q || root == nullptr) return root;// 后序遍历TreeNode *left = lowestCommonAncestor(root->left, p, q);TreeNode *right = lowestCommonAncestor(root->right, p, q);// 中间结点的处理// 左右都非空表示，该节点为公共祖先结点 if (left != nullptr && right != nullptr)return root;// 有一个为空表示，if (left == nullptr) return right;if (right == nullptr) return left;return root;
}

110. 判断平衡二叉树（后序遍历的示例）

递归法

给定一个二叉树，判断它是否是高度平衡的二叉树。
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

// 初始化ans为true，最后看ans是否为false即可
int depth(TreeNode* root, bool &ans) {if(!root) return 0;// 后序遍历int left=1+depth(root->left, ans);int right=1+depth(root->right, ans);if(abs(left-right) > 1) ans = false;// 对根结点的处理// 递归出口return max(left,right);	// 返回树的高度
}
// 尾递归优化：效率高
bool isBalanced(TreeNode* root) {if (root == nulllptr)  return true;return 	abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}

222. 求树中结点的数量

题目
- 给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

算法

int getNodesNum(TreeNode* cur) {if (cur == NULL) return 0;int leftNum = getNodesNum(cur->left);      // 左int rightNum = getNodesNum(cur->right);    // 右int treeNum = leftNum + rightNum + 1;      // 中return treeNum;
}

226. 翻转二叉树

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

TreeNode* invertTree(TreeNode* root) {auto self = [&](auto &&self, TreeNode *root){if (root == nullptr) return ;self(self, root->left);self(self, root->right);swap(root->left, root->right);return ;};self(self, root);return root;
}

101. 对称二叉树

题目
- 求一颗二叉树是否镜像对称
思路
- 根节点必定对称，关键是左右两子树的对称
- 左右两个孩子存在的情况下，递归比较左右两颗子树的情况

bool isSymmetric(TreeNode* root) {auto self = [&](auto && self, TreeNode *left, TreeNode *right)->bool{// 递归出口if (left == nullptr && right == nullptr) return true;else if (left != nullptr && right == nullptr) return false;else if (left == nullptr && right != nullptr) return false;else if (left->val != right->val) return false;// 后序遍历：递归比较并汇总结果bool outside = self(self, left->left, right->right);bool inside = self(self,left->right, right->left);bool is_same = outside && inside;// 返回结果return is_same;};return self(self, root->left, root->right);
}

左叶子之和

求二叉树的左叶子之和

遍历所有节点，对所求的特殊节点进行约束求值

if (node->left != nullptr 
&& node->left->left == nullptr 
&& node->left->right == nullptr)res += node->left->val;

二叉树的所有路径（带缓存的前序遍历）

递归

数字转化成字符串to_string(number)
字符串后追加子串str.append(subStr)
字符串删除某个位置之后的字符str.erase(position)

// 数字型
void dfs(TreeNode*root,vector<int>path, vector<vector<int>> &res) {if(!root) return;  //根节点为空直接返回// 中path.push_back(root->val);  //作出选择if(!root->left && !root->right) //如果到叶节点  {res.push_back(path);return;}// 左dfs(root->left,path,res);  //继续递归// 右dfs(root->right,path,res);
}
// 字符型
void binaryTree(TreeNode* root,string path,vector<string>&res) {if(root==NULL) return ;path.append(to_string(root->val));path.append("->");if(root->left==NULL&&root->right==NULL{path.erase(path.length()-2);res.push_back(path);}binaryTree(root->left,path,res);binaryTree(root->right,path,res);
}
vector<string> binaryTreePaths(TreeNode* root) {string path;vector<string>res;binaryTree(root,path,res);return res;
}

符合总和的路径

题目

判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true；否则，返回 false

// 递归方式：前序遍历，并记录每条路径的和
bool hasPathSum(TreeNode* root, int targetSum) {bool flag = false;auto self = [&](auto &&self, TreeNode *root, int sum){// sum不可全局if (root == nullptr) return ;// 根结点的处理sum += root->val;cout << sum << ' ';if (root->left == nullptr && root->right == nullptr && targetSum == sum) flag = true;self(self, root->left, sum);self(self, root->right, sum);};self(self, root, 0);return flag;
}
// 非递归
bool hasPathSum(TreeNode* root, int targetSum) {// 初始化stack<TreeNode*> st;if(root != nullptr) st.push(root);int sum = 0;// 迭代while(!st.empty()){TreeNode *cur = st.top();if(cur != nullptr){st.pop();st.push(cur);st.push(nullptr);sum += cur->val;if(cur->right) st.push(cur->right);if(cur->left) st.push(cur->left);}else{st.pop();cur = st.top();st.pop();// 节点判断if(sum == targetSum&& cur->left == nullptr && cur->right == nullptr){return true;}else{// 回溯sum -= cur->val;}}}return false;
}