频道栏目
首页 > 考试 > 其他 > 正文
【LeetCode101-110】二叉树对称及存储,前序中序遍历生成二叉树,中序后序生成二叉树,数组转化为AVL平衡树,判断二叉树是否平衡
2017-04-24 09:53:41         来源:朱铭德的博客  
收藏   我要投稿

101.二叉树是否对称【easy】

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree[1,2,2,3,4,4,3]is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following[1,2,2,null,3,null,3]is not:

    1
   / \
  2   2
   \   \
   3    3

和100题思路一样,通过迭代来判断左右两个自树是否对称……

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
         if(!root)return true;
         if(help(root->left,root->right))return true;
         return false;
    }
    bool help(TreeNode*left,TreeNode*right){
        if(!left&&right||left&&!right)return false;
        if(!left&&!right)return true;
        if(!help(left->left,right->right))return false;
        if(left->val!=right->val)return false;
        if(!help(left->right,right->left))return false;
        return true;
    }
};


102.按层级存储二叉树【medium】

Given a binary tree, return thelevel ordertraversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

还是一样的思路,构造一个函数不断迭代……一个变量判断应该存储再哪一行…

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector>result;
        help(result,root,0);
        return result;
    }
    void help(vector>&result,TreeNode*root,int level){
        if(!root)return;
        if(root){
            vectortemp;
            if(level+1>result.size()){
                temp.push_back(root->val);
                result.push_back(temp);
            }
            else result[level].push_back(root->val);
        }
        help(result,root->left,level+1);
        help(result,root->right,level+1);
        return;
    }
};


103.按层存储二叉树,偶数层逆序

就在上一题的基础之上把偶数层逆序就好了……

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector> zigzagLevelOrder(TreeNode* root) {
        vector>result;
        help(result,root,0);
        for(int i=1;i>&result,TreeNode*root,int level){
        if(!root)return;
        if(root){
            vectortemp;
            if(level+1>result.size()){
                temp.push_back(root->val);
                result.push_back(temp);
            }
            else result[level].push_back(root->val);
        }
        help(result,root->left,level+1);
        help(result,root->right,level+1);
        return;
    }
};


104.返回二叉树最长长度【easy】

迭代下就好了……

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)return 0;
        if(!root->right&&!root->left)return 1;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

105.前序遍历&中序遍历生成二叉树

前序遍历NLR preorder 根左右

中序遍历LNR inorder 左根右

后续遍历LRN postorder 左右根

class Solution {
public:
	TreeNode* buildTree(vector& preorder, vector& inorder) {
		//根据前序以及中序确定一个二叉树
		if (preorder.size() == 0)return nullptr;
		TreeNode *temp = new TreeNode(preorder[0]);

		int length = find(inorder.begin(), inorder.end(), preorder[0]) - inorder.begin();


		if (length>0) {
			vectorpreorder2(preorder.begin() + 1, preorder.begin() + 1 + length);
			vectorinorder2(inorder.begin(), inorder.begin() + length);
			temp->left = buildTree(preorder2, inorder2);
		}

		if (preorder.end() - preorder.begin() - 1 - length>0) {
			vectorpreorder3(preorder.begin() + 1 + length, preorder.end());
			vectorinorder3(inorder.begin() + length+1 , inorder.end());
			temp->right = buildTree(preorder3, inorder3);
		}

		return temp;
	}
};

106.中序遍历&后序遍历生成二叉树

上面的稍微改一下就好了……

class Solution {  
public:  
    TreeNode* buildTree(vector& inorder, vector& postorder) {  
        //根据中序和后序确定二叉树
        //中序:左根右      后序:左右根
        if (postorder.size() == 0)return nullptr;  
        TreeNode *temp = new TreeNode(postorder.back());  
  
        int length = find(inorder.begin(), inorder.end(),postorder.back()) - inorder.begin();  
  
  
        if (length>0) {  
            vectorpostorder2(postorder.begin(), postorder.begin() + length);  
            vectorinorder2(inorder.begin(), inorder.begin() + length);  
            temp->left = buildTree( inorder2,postorder2);  
        }  
  
        if (postorder.end() - postorder.begin() - 1 - length>0) {  
            vectorpostorder3(postorder.begin()  + length, postorder.end()-1);  
            vectorinorder3(inorder.begin() + length+1 , inorder.end());  
            temp->right = buildTree( inorder3,postorder3);  
        }  
  
        return temp;  
    }  
}; 



107.二叉树按级存储(逆序)

在102的基础上加一行reverse就好了……

class Solution {
public:
    vector> levelOrderBottom(TreeNode* root) {
        vector>result;
        help(result,root,0);
        reverse(result.begin(),result.end());
        return result;
    }
    void help(vector>&result,TreeNode* root,int level){
        if(!root)return;
            if(root){
            if(level+1>result.size()){
                vectortemp;
                temp.push_back(root->val);
                result.push_back(temp);
            }
            else result[level].push_back(root->val);
        }
        help(result,root->left,level+1);
        help(result,root->right,level+1);
        return;
    }
};


108.有序数组转化为AVL树【easy】

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

一开始的代码结果是这样的(32/32....)

\

代码是这样的:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	TreeNode* sortedArrayToBST(vector& nums) {
		if (nums.size() == 0)return nullptr;
		vectortemp;
		for (int i = 0; i&temp, int rounds, int max) {
		int begin = pow(2, rounds) - 1; int end = pow(2, rounds + 1) - 2;
		if (2 * begin + 1 > max)return;
		for (int i = begin; i <= end; ++i) {
			if (2 * i + 1 <= max)temp[i]->left = temp[2 * i + 1];
			else break;
			if (2 * i + 2 <= max)temp[i]->right = temp[2 * i + 2];
			else break;
		}
		help(temp, rounds + 1, max);
	}

	void help2(TreeNode* temp, vectornums, int &i) {
		if (!temp)return;
		help2(temp->left, nums, i);
		temp->val = nums[i];
		++i;
		help2(temp->right, nums, i);
	}
};

然后转换了下思路……发现用Vector太耗费空间了,所有直接迭代就好了……很简洁

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector& nums) {
        return sortedArrayToBST(nums,0,nums.size());
    }
    TreeNode* sortedArrayToBST(vector& nums,int begin,int size) {
        if(size<=0)return nullptr;
        TreeNode *temp=new TreeNode(nums[begin+size/2]);
        temp->left=sortedArrayToBST(nums,begin,size/2);
        temp->right=sortedArrayToBST(nums,begin+size/2+1,(size+1)/2-1);
        return temp;
    }
};

109.单链表转化为AVL树

把链表转化为vector,和上一题一样了…,需要O(n)空间…

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        //先试试转化为vector会不会超空间……
        vectortemp;
        while(head){
            temp.push_back(head->val);
            head=head->next;
        }
       return sortedArrayToBST(temp,0,temp.size());
    }
    TreeNode* sortedArrayToBST(vector& nums,int begin,int size) {
        if(size<=0)return nullptr;
        TreeNode *temp=new TreeNode(nums[begin+size/2]);
        temp->left=sortedArrayToBST(nums,begin,size/2);
        temp->right=sortedArrayToBST(nums,begin+size/2+1,(size+1)/2-1);
        return temp;
    }
};

别人的O(1)空间的方法,关键是中序遍历!!!
class Solution {
public:
    ListNode *list;
    int count(ListNode *node){
        int size = 0;
        while (node) {
            ++size;
            node = node->next;
        }
        return size;
    }
    
    TreeNode *generate(int n){
        if (n == 0)
            return NULL;
        TreeNode *node = new TreeNode(0);
        node->left = generate(n / 2);
        node->val = list->val;
        list = list->next;
        node->right = generate(n - n / 2 - 1);
        return node;
    }
    
    TreeNode *sortedListToBST(ListNode *head) {
        this->list = head;
        return generate(count(head));
    }
};

110.判断二叉树是否是平衡的(所有左右子树长度差不超过1)

我的方法:(写的时候就觉得其中有很多冗余,但是通过了……O(n2)

因为每次都要调用一个深度函数length()

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root)return true;
        if(abs(length(root->left)-length(root->right))<=1&&isBalanced(root->left)&&isBalanced(root->right))return true;
        return false;
    }
    int length(TreeNode* root){
        if(!root)return 0;
        if(!root->left&&!root->right)return 1;
        return max(length(root->left),length(root->right))+1;
    }
};
但其实只要有一个子树不满足,整个就不满足了,所有完全可以在深度函数里有所表示

下面就是参考别人的O(n)的方法//DFS,深度优先的搜索……

class Solution {
public:
int dfsHeight (TreeNode *root) {
        if (root == NULL) return 0;
        
        int leftHeight = dfsHeight (root -> left);
        if (leftHeight == -1) return -1;
        int rightHeight = dfsHeight (root -> right);
        if (rightHeight == -1) return -1;
        
        if (abs(leftHeight - rightHeight) > 1)  return -1;
        return max (leftHeight, rightHeight) + 1;
    }
    bool isBalanced(TreeNode *root) {
        return dfsHeight (root) != -1;
    }
};
点击复制链接 与好友分享!回本站首页
上一篇:LeetCode_198、213、222三题
下一篇:编程题 对公司上万名员工按照年龄排序
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站