[数据结构]：7.二叉树练习习题

[数据结构]7.二叉树练习习题前言一翻转二叉树题目描述思路解答代码二平衡二叉树题目描述思路解答代码前言嗨我是firdawn本章将介绍一些二叉树练习习题帮助我们巩固二叉树的知识点。下面是本章的思维导图那么让我们开始吧一翻转二叉树题目描述翻转二叉树是LeetCode上的一道题题目要求为给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。思路题目要求我们翻转二叉树每一个子节点左右子树因为它遍历了二叉树的每个节点并且对每个节点都是翻转左右子树那么我们可以用递归的方法实现将二叉树分为根左子树右子树。对于当前节点翻转它的左右子树然后再翻转它的左子树和右子树。解答代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */// //前序遍历// struct TreeNode* invertTree(struct TreeNode* root) {// if(rootNULL)// {// return NULL;// }// struct TreeNode* tmproot-left;// root-leftroot-right;// root-righttmp;// invertTree(root-left);// invertTree(root-right);// return root;// }//后序遍历structTreeNode*invertTree(structTreeNode*root){if(rootNULL){returnNULL;}structTreeNode*tmproot-right;root-rightinvertTree(root-left);root-leftinvertTree(tmp);returnroot;}二平衡二叉树题目描述平衡二叉树题目要求为给定一个二叉树判断它是否是平衡二叉树1。思路因为它需要遍历二叉树所有节点并且判断当前节点下的左右子树高度差值所以我们同样可以用递归判断。二叉树分为根节点左子树右子树我们可以在当前根节点下判断左右子树高度差值是否满足不超过1的条件如果满足就继续判断左右子树的下的子树高度差值不满足就返回false。如果根节点下的左右子树差值满足并且左右子树的子树差值满足题目条件那么就说明这棵树是平衡二叉树。解答代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */intgetDepth(structTreeNode*root){if(rootNULL){return0;}intLeftDepthgetDepth(root-left);intrightDepthgetDepth(root-right);intDepthLeftDepthrightDepth?LeftDepth:rightDepth;//取左右子树深度更高的为子树深度return1Depth;}intabsVal(intx,inty){returnxy?x-y:y-x;}boolisBalanced(structTreeNode*root){if(rootNULL){returntrue;}intLeftDepthgetDepth(root-left);intrightDepthgetDepth(root-right);if(absVal(LeftDepth,rightDepth)1){returnfalse;}returnisBalanced(root-left)isBalanced(root-right);}是指该树所有节点的左右子树高度相差不超过1。 ↩︎