数据结构与算法再探（三）树

目录

二叉树

二叉树遍历

C++ 递归

C++迭代

 python递归

层次遍历

二叉树的最大深度及直径

python 版递归树深度

递归求宽度

反转二叉树

python递归实现

 代码可视化

---

二叉树

二叉树遍历

C++ 递归

通过调用自身来解决问题，将原问题分解为一个或多个规模较小的相似子问题，在函数体内调用自身来解决问题。递归算法需要定义基本情况（边界条件），以防止无限递归。

class Solution {
public:void preorder(TreeNode *root, vector<int> &res) {if (root == nullptr) {return;}res.push_back(root->val); #先根preorder(root->left, res);// res.push_back(root->val); #中preorder(root->right, res);//res.push_back(root->val); #后}vector<int> preorderTraversal(TreeNode *root) {vector<int> res;preorder(root, res);return res;}
};

C++迭代

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;if (!root) {return res;}stack<TreeNode*> stk;stk.push(root);while (stk.size()) {auto node = stk.top();stk.pop();res.push_back(node->val);if (node->right) {stk.push(node->right);}if (node->left) {stk.push(node->left);}}return res;}
};

 python递归

class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:def dfs(root):if not root:returnres.append(root.val) #改变位置进行先、中、后、遍历dfs(root.left)dfs(root.right)res=[]dfs(root)return res

层次遍历

637. 二叉树的层平均值 - 力扣（LeetCode）

vector<double> averageOfLevels(TreeNode* root) {vector<double> ans;if(!root){return ans;}queue<TreeNode*> q;q.push(root);while(!q.empty()){int count=q.size();double sum=0;for(int i=0;i<count;++i){TreeNode* node=q.front();q.pop();sum+=node->val;if(node->left){q.push(node->left);}if(node->right){q.push(node->right);}}ans.push_back(sum/count);}return ans;
}

二叉树的最大深度及直径

python 版递归树深度

递归虽然简洁但是有时难以写出和理解，每一次的递归调用都是一次完成函数的调用，需要梳理在递归临界点返，和返回后函数继续执行后最后，还要梳理回到上一次的递归调用节点间继续调用，着实难以理解，但是递归很多适用于树的操作。

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if root is None:return 0ld=self.maxDepth(root.left)rd=self.maxDepth(root.right)return max(ld,rd)+1
#递归子问题返回结果给上一级，不能陷入直观上的顺序执行，return max(ld,rd)+1却决于左右子树是否
#有节点，这个返回值第一次返回时也许经历了很多次的函数压栈，多次调用

递归求宽度

543. 二叉树的直径

class Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:self.res=0def dfs(root):if not root: return 0ld=dfs(root.left)rd=dfs(root.right)self.res=max(self.res,ld+rd)return max(ld,rd)+1dfs(root)return self.res

反转二叉树

翻转二叉树

python递归实现

class Solution:def flipTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:returntemp=root.leftroot.left, root.right=self.flipTree(root.right),self.flipTree(temp)return root

 代码可视化

通过可视化发现为什么临时变量保存左节点，以及临时变量在递归中的变化

 代码可视化