Leetcode-二叉树

Leetcode-二叉树

二叉树

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

class Solution {
public:
    vector<int> result;
    void inorder(TreeNode* root){
        if(root == NULL){
            return;
        }
        inorder(root->left);
        result.push_back(root->val);
        inorder(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        inorder(root);
        return result;
    }
};

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int> > result;
        if(root == NULL){
            return result;
        }
        queue<TreeNode*> q;
        q.push(root);
        int sign = 0;
        while(!q.empty()){
            int t = q.size();
            vector<int> temp;
            for(int i=0;i<t;i++){
                TreeNode* x = q.front();
                q.pop();
                temp.push_back(x->val);
                if(x->left != NULL){
                    q.push(x->left);
                }
                if(x->right != NULL){
                    q.push(x->right);
                }
            }
            if(sign == 1){
                reverse(temp.begin(), temp.end());
            }
            result.push_back(temp);
            sign = 1 - sign;
        }
        return result;
    }
};