一、镜像二叉树

原二叉树

镜像二叉树

解法一:递归(推荐)

采用后序遍历,自底向上进行值的交换

• 先深度最左端的节点，遇到空节点返回
• 进入子树最右端
• 返回父问题，交换父问题两节点的值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot==NULL)
            return NULL;
        TreeNode*left=Mirror(pRoot->left),
        *right=Mirror(pRoot->right);//递归子树
        pRoot->left=right;//交换
        pRoot->right=left;
        return pRoot;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度:O(n),访问二叉树所有节点
空间复杂度:O(n),递归栈最大深度为n

解法二:栈

栈是自顶向下访问

• 判断树是否为空
• 使用辅助栈遍历二叉树，根节点先进
• 遍历时每次弹出一个栈中元素，将该元素节点的左右节点入栈，同时交换二者的值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot==NULL)
            return NULL;
        stack<TreeNode*>s;
        s.push(pRoot);
        while(!s.empty())
        {
            TreeNode*tmp=s.top();
            s.pop();
            if(tmp->left)//左右子节点不为空入
                s.push(tmp->left);
            if(tmp->right)
                s.push(tmp->right);
            swap(tmp->left,tmp->right);//交换左右系欸但
        }
        return pRoot;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度:O(n),访问二叉树所有节点
空间复杂度:O(n)，最坏情况下栈的大小为n

二、判断是否为二叉搜索树

二叉搜索树是每个左子树节点值小于根节点，每个右子树节点大于根节点，中序遍历即为递增顺序

解法一:递归(推荐)

• 递归到最左，初始化pre
• 遍历整棵二叉树，连接pre与当前节点，并更新pre
• 左子树若不是二叉搜索树返回false
• 判断当前节点是否小于前置节点，更新前置节点
• 最后由右子树的后面节点决定

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    long pre=INT_MIN;
    bool isValidBST(TreeNode* root) {
        // write code here
        if(root==NULL)
            return true;
        if(!isValidBST(root->left))//先进左子树
            return false;
        if(root->val<=pre)
            return false;
        pre=root->val;//更新节点值
        if(!isValidBST(root->right))//再进右子树
            return false;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度:O(n),n为二叉树节点数，遍历整个二叉树
空间复杂度:O(n),最坏情况二叉树退化为链表，递归栈深度为n

解法二:非递归

• 先判断树是否为空
• 准备一个数组记录中序遍历的结果
• 创建辅助栈，当二叉树节点为空且栈中没有节点时停止访问
• 从根节点开始，优先进入每棵子树最左边的一个节点，将其加入栈中，保存父问题
• 到达最左后，可开始访问，若还存在右节点，则右节点入栈，其右子树的访问也是优先到最左
• 遍历数组，依次比较相邻两个元素是否为递增序

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isValidBST(TreeNode* root) {
        // write code here
        stack<TreeNode*>s;
        TreeNode*head=root;
        vector<int>v;
        while(head!=NULL||!s.empty())
        {
            while(head!=NULL)//直到无左节点
            {
                s.push(head);
                head=head->left;
            }
            head=s.top();
            s.pop();
            v.push_back(head->val);
            head=head->right;
        }
        for(int i=1;i<v.size();i++)
        {
            if(v[i-1]>v[i])//存在降序，则不是搜索树
                return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

时间复杂度:O(n),二叉树节点数n
空间复杂度:O(n),辅助栈及辅助空间

三、判断是否为完全二叉树

完全二叉树指叶子节点只能出现在最下层或次下层

层次遍历(推荐)

• 优先判断树是否为空
• 初始化一个队列辅助层次遍历，将根节点加入队列中
• 从队列中弹出节点，若遇到某个节点为空，进行标记，若后续还能访问，则说明提前出现了叶子节点
• 否则，继续加入左右子节点进入队列排队

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isCompleteTree(TreeNode* root) {
        // write code here
        if(root==NULL)
            return true;
        queue<TreeNode*>q;
        q.push(root);
        bool flag=false;
        while(!q.empty())
        {
           int n=q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode*node=q.front();
                q.pop();
                if(node==NULL)//标记第一次遇到空节点
                    flag=true;
                else//后续访问已遇到空节点，说明经过了叶子，若还存在非空节点，直接返回false
                {
                    if(flag)
                        return false;
                    q.push(node->left);
                    q.push(node->right);
                }
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

时间复杂度：O(n)，其中n为二叉树节点数，层次遍历最坏情况下遍历每一个节点
空间复杂度：O(n)，最坏情况下，层次队列的最大空间为O(n)

四、判断是否为平衡二叉树

平衡二叉树任意节点两边子树深度相差不超过1

解法一:自顶向下

• 创建第一个函数递归遍历二叉树所有节点
• 对每个节点调用第二个函数获取子树深度
• 创建的子树深度获取函数，只需向下深度遍历，累加左右深度较大值
• 根据深度判断是否为平横二叉树

class Solution {
public:
    int depth(TreeNode*root)
    {
        if(root==NULL)
            return 0;
        int left=depth(root->left),//递归算出左右子树深度
        right=depth(root->right);
        return max(left,right)+1;//取最大值+1
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot==NULL)
            return true;
        int left=depth(pRoot->left),
        right=depth(pRoot->right);
        if(abs(left-right)>1)//深度差值大于一不为平衡树
            return false;
        return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
        //在对左右子树递归判断
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度:O(n^2),两个递归最深都为n
空间复杂度:O(n),递归栈最大深度

解法二:自底向上(推荐)

自顶向上存在弊端，时间复杂度较高，自底向上可同时完成深度计算与判断

• 先判断空树
• 递归计算深度同时判断是否为平衡二叉树
• 递归计算当前节点左右子树高度差，比较深度
• 每次递归将深度结果回传，就可以边判断边计算深度

class Solution {
public:
    bool Judge(TreeNode*root,int&depth)
    {
        if(root==NULL)
        {
            depth=0;
            return true;
        }
        int left=0,right=0;
        if(Judge(root->left, left)==false||
           Judge(root->right, right)==false)//左右子树判断
            return false;
        if(abs(left-right)>1)//判断
            return false;
        depth=max(left,right)+1;
        return true;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth=0;
        return Judge(pRoot,depth);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度:O(n),递归n个节点
空间复杂度:O(n),递归栈深度