Leetcode 100.101.110.199 二叉树相同/对称/平衡 C++实现

Leetcode 100. 相同的树

问题：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/

算法：判断根结点，如果都为空则相等，返回 true 。如果有一个为空，则 p == q 一定不成立，返回 false 。如果都不为空，则 if 条件不成立，判断根结点的值 val 、左子树、右子树是否相等。

代码：

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(p == nullptr || q  == nullptr)    return p == q;// 如果pq都为空，则返回true，如果有一个为空则p == q不成立，返回falsereturn p->val == q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right);// 都不为空则判断值相等、左右子树相同}
};

Leetcode 101. 对称二叉树

问题：给你一个二叉树的根节点 root ， 检查它是否轴对称。

算法：根节点不用判断，只需判断左子树的右子树和右子树的左子树是否相等，以及左子树的左子树和右子树的右子树是否相等即可。

代码：

class Solution {// 在【100. 相同的树】的基础上稍加改动bool isSameTree(TreeNode *p, TreeNode *q) {if (p == nullptr || q == nullptr)    return p == q;return p->val == q->val && isSameTree(p->left, q->right) && isSameTree(p->right, q->left);}public:bool isSymmetric(TreeNode* root) {return isSameTree(root->left,root->right);}
};

Leetcode 110. 平衡二叉树

问题：给定一个二叉树，判断它是否是平衡二叉树。

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1 。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/

算法：递归左右子树，得出深度。在过程中，如果检测出有子树不是平衡二叉树，则 return -1 ，一层层向上 return ，如果是平衡二叉树则 return 最大深度。

代码：

class Solution {int get_height(TreeNode* node){if(node == nullptr) return 0;// 空结点则returnint left_depth = get_height(node->left);// 左子树深度if(left_depth == -1)    return -1;// 遇到 -1 就 returnint right_depth = get_height(node->right);// 右子树深度if(right_depth == -1 || abs(left_depth - right_depth) >1)   return -1;//绝对值 > 1 表明不是平衡二叉树，也return -1return max(left_depth,right_depth) + 1;// 返回最大深度}
public:bool isBalanced(TreeNode* root) {return get_height(root) != -1;// 如果是 -1 证明不是平衡二叉树，return false ，不是 -1 则证明是平衡二叉树，返回 true}
};

Leetcode 199. 二叉树的右视图

问题：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/

算法：从根结点 root 开始，利用返回数组 ans 的 size 来判断是否已经有右边的结点填入到数组 ans 中，如果已经填入则跳到下一深度。

代码：

class Solution {vector<int> ans;void dfs(TreeNode* node,int depth){if(node == nullptr) return;if(depth == ans.size()) ans.push_back(node->val);// 这个深度首次遇到dfs(node->right,depth + 1);// 先递归右子树dfs(node->left,depth + 1);}
public:vector<int> rightSideView(TreeNode* root) {dfs(root,0);return ans;}
};