重拾数据结构之二叉树

1、Maximum Depth of Binary Tree （计算二叉树的深度）
Solution：

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };


class Solution {
public:
    int maxDepth(TreeNode* root) {
        
        if (root == NULL){
            return 0;
        }
        
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        
        return l > r ? l + 1:r + 1;
    }
};

2、Invert Binary Tree （反转二叉树）
Solution：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        
        if ( root == NULL){
            return NULL;
        }
        
        //change left node and right node
        TreeNode *tmpNode = root->left;
        root->left = root->right;
        root->right = tmpNode;
        
        invertTree(root->left);
        invertTree(root->right);
        
        return root;
    }
};

3、Balanced Binary Tree （平衡二叉树判断）
Solution：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    int height(TreeNode* root) {
        
        if(root==NULL){
            return 0;
        }else{
            int l=height(root->left);
            int r=height(root->right);
            return 1+((l>r)?l:r);
        }
    }
    
    bool isBalanced(TreeNode *root) {
        
        if(root==NULL){
            
            return true;
            
        }else{
            
            int l,r;
            
            l=height(root->left);
            r=height(root->right);
            
            if((l > r+1)||(r > l+1)){
                return false;
            }else{
                return isBalanced(root->left)&&isBalanced(root->right);
            }
        }
    }
};

二叉树：https://blog.csdn.net/fansongy/article/details/6798278