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

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

---

---

😊点此到文末惊喜↩︎

基础知识

二叉树DFS基本算法

递归算法

1. 注意
   • 左右子树不需要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);// 中
   }
   

非递归算法

1. 注意点

   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. 二叉树的最近公共祖先

1. 题目
   • 给定一个二叉树, 找到该树中两个指定节点p和q的最近公共祖先。
2. 复杂度分析：
   • 时间复杂度 O(N)： 其中 N为二叉树节点数；最差情况下，需要递归遍历树的所有节点。
   • 空间复杂度 O(N)： 最差情况下，递归深度达到 N
3. 思路
   • 递归出口：如果不是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. 递归法
   • 给定一个二叉树，判断它是否是高度平衡的二叉树。
   • 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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. 求树中结点的数量

1. 题目
   • 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
2. 算法

   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. 翻转二叉树

1. 给你一棵二叉树的根节点 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. 对称二叉树

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

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);
}

左叶子之和

1. 求二叉树的左叶子之和
   • 遍历所有节点，对所求的特殊节点进行约束求值

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

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

1. 递归
   • 数字转化成字符串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;
   }
   

符合总和的路径

1. 题目
   • 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 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;
   }
   

---

少年，我观你骨骼清奇，颖悟绝伦，必成人中龙凤。 不如点赞·收藏·关注一波

---

🚩点此跳转到首行↩︎

参考博客

1. 「代码随想录」47. 全排列 II:【彻底理解排列中的去重问题】详解
2. codetop
3. 力扣（LeetCode）Krahets