LeetCode探索——二叉树

二叉树的遍历

• 二叉树的前序遍历**

class Solution{
    public:
    vector<int> preorderTraversal(TreeNode* root){
        if(!root) return{};

        vector<int> res;
        vector<int> temp;

        res.push_back(root->val);

        temp = preorderTraversal(root->left);
        res.insert(res.end(),temp.begin(),temp.end());

        temp = preorderTraversal(root->right);
        res.insert(res.end(),temp.begin(),temp.end());

        return res;
    }
};

• 二叉树的中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        vector<int> temp;
        
        if(!root) return {};
        
        temp=inorderTraversal(root->left);
        res.insert(res.end(),temp.begin(),temp.end());
        
        res.push_back(root->val);
        
        temp=inorderTraversal(root->right);
        res.insert(res.end(),temp.begin(),temp.end());  
        
        return res;
    }
};

• 二叉树的后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        vector<int> temp;
        
        if(!root) return {};
        
        temp=postorderTraversal(root->left);
        res.insert(res.end(),temp.begin(),temp.end());

        temp=postorderTraversal(root->right);
        res.insert(res.end(),temp.begin(),temp.end());  
        
        res.push_back(root->val);
        
        return res;
    }
};

• 二叉树的层次遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > res;
        if(!root) return {};
        
        queue<TreeNode*> q;     // 初始化队列
        q.push(root);           // 根结点入队列 第一步
        
        while (!q.empty()) {
            int currentLevelSize = q.size();
            res.push_back(vector <int> ());
            
            for(int i=0;i<currentLevelSize;++i){        // 遍历
                auto node = q.front();
                q.pop();
                res.back().push_back(node->val);
                if (node->left)                         // 第二步
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);                // 第三步
            }
        }
        return res;
    }
};

二叉树的深度与路径

• 二叉树最大深度

// 自顶向下
int answer;		       // 初始化answer
void maximum_depth(TreeNode* root, int depth) {
    if (!root) {
        return;
    }
    if (!root->left && !root->right) {
        answer = max(answer, depth);
    }
    maximum_depth(root->left, depth + 1);
    maximum_depth(root->right, depth + 1);
}

// 自底向上
int maximum_depth(TreeNode* root) {
	if (!root) {
		return 0;                                 
	}
	int left_depth = maximum_depth(root->left);
	int right_depth = maximum_depth(root->right);
	return max(left_depth, right_depth) + 1;	  
}

递归

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

• 对称二叉树

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return (!root) ? true : dfs(root->left, root->right);
    }
    bool dfs(TreeNode* p1, TreeNode* p2) {
        if (!p1 || !p2) return !p1 && !p2; //一个为空返回false，两个为空返回true
        return p1->val == p2->val && dfs(p1->left, p2->right) && dfs(p1->right, p2->left);
    }
};

• 路径总和

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;			// 树为空
        if(root->val==sum && !root->left && !root->right)		// 树只有一个根节点
            return true;
        return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);
    }
};

构造二叉树

• 从中序与后序遍历序列构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        
    }
    
};

• 从前序与中序遍历序列构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
    TreeNode* helper(vector<int>& pre, vector<int>& inorder,int pre_start,int pre_end,int inorder_start,int inorder_end){
        if(pre_start > pre_end || inorder_start > inorder_end){return NULL};
        TreeNode* root=new TreeNode(pre[pre_start]);  	// 构造根节点
        if(pre_start==pre_end){return root;}			// 只有一个节点
        
        int index=inorder_start;
        while(pre[pre_start]!=inorder[index]){
            index++;									// 记录中序遍历序列中根节点的位置
        }
        
        root->left=helper(pre,inorder,pre_start+1,pre_start+1+index-1-inorder_start,inorder_start,index-1);
        root->right=helper(pre,inorder,pre_start+1+1+index-1-inorder_start,pre_end,index+1,inorder_end);
        return root;
    }
};

• 从前序和后序遍历序列构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& postorder) {
        
    }
};