首页 > 代码库 > leetcode[110] Balanced Binary Tree
leetcode[110] Balanced Binary Tree
判断一棵树是不是平衡二叉树。
思路：递归。
每个节点的左右子树是平衡二叉树，并且左右子树的高度相差不超过一。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int heightTree(TreeNode *root) { if (!root) return 0; int lf = 0, ri = 0; if (root -> left) lf = heightTree(root -> left); if (root -> right) ri = heightTree(root -> right); return max(lf, ri) + 1; } bool isBalanced(TreeNode *root) { if (!root) return true; bool lf, ri; lf = isBalanced(root -> left); ri = isBalanced(root -> right); return lf && ri && (abs(heightTree(root->left)-heightTree(root->right))<=1); }};
思路二：利用中序遍历，对每个节点进行左子树右子树高度相差值进行判断。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int heightTree(TreeNode *root) { if (!root) return 0; int lf = 0, ri = 0; if (root -> left) lf = heightTree(root -> left); if (root -> right) ri = heightTree(root -> right); return max(lf, ri) + 1; } bool isBalanced(TreeNode *root) { if (!root) return true; stack<TreeNode *> sta; TreeNode *p = root; while(p || !sta.empty()) { while(p) { sta.push(p); p = p -> left; } if (!sta.empty()) { p = sta.top(); sta.pop(); if (abs(heightTree(p -> left) - heightTree(p -> right)) > 1) return false; p = p -> right; } } return true; }};
leetcode[110] Balanced Binary Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。