二叉树

递归遍历（前序）

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* result = (int *)malloc(100 * sizeof(int));
    * returnSize = 0;
    traversal(root, returnSize, result);
    return result;
}
void traversal(struct TreeNode* root, int* p, int* result){
    if(root){
        *(result + *p) = root->val;
        (*p)++;
        traversal(root->left, p, result);
        traversal(root->right, p, result);
    }
}

class Solution {
    List r;
    Solution(){
        r = new ArrayList();
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        trans(root);
        return r;
    }
    public void trans(TreeNode root){
        if(root != null){
            r.add(root.val);
            trans(root.left);
            trans(root.right);
        }
    }
}

非递归遍历（中序）

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int* result = (int *)malloc(100 * sizeof(int));
    *returnSize = 0;
    Traversal(root, returnSize, result);
    return result;
}
void Traversal(struct TreeNode* root, int* p, int* result){
    struct TreeNode** stack[100] = {};
    int stackSize = 0;
    while(root || stackSize > 0){
        while(root){
            stack[stackSize] = root;
            stackSize++;
            root = root->left;
        }
        if(stackSize != 0){
            stackSize--;
            root = stack[stackSize];
            *(result + *p) = root->val;
            (*p)++;
            root = root->right;
        }
    }
}

class Solution {
    List l;
    Stack s;
    Solution(){
        l = new ArrayList();
        s = new Stack<TreeNode>();
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        trans(root);
        return l;
    }
    public void trans(TreeNode root){
        while(root != null || !s.isEmpty()){
            while(root != null){
                s.add(root);
                root = root.left;
            }
            if(!s.isEmpty()){
                root = (TreeNode)s.pop();
                l.add(root.val);
                root = root.right;
            }
        }
    }
}

非递归遍历（后序）

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* temp = malloc(100 * sizeof(int));
    *returnSize = 0;
    traversal(root, returnSize, temp);
    int* result = malloc(100 * sizeof(int));
    int count = *returnSize;
    int p = 0;
    while(count > 0){
        *(result + p) = *(temp + count - 1);
        count--;
        p++;
    }
    return result;
}
 void traversal(struct TreeNode* root, int* returnSize, int* result){
    struct TreeNode** stack[100] = {};
    int p = 0; //栈中元素个数
    while(root || p != 0){
        while(root){
            stack[p] = root;
            p++;
            *(result + *returnSize) = root->val;
            (*returnSize)++;
            root = root->right;
        }
        if(p != 0){
            p--;
            root = stack[p];
            root = root->left;
        }
    }
}

/*使用两个堆栈，将根结点-右儿子-左儿子的顺序颠倒即为后续遍历
根结点-右儿子-左儿子的顺序只需简单改变非递归前序遍历*/
class Solution {
    List l;
    Stack s;
    Stack r;
    Solution(){
        l = new ArrayList();
        s = new Stack<TreeNode>();
        r = new Stack<TreeNode>();
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        trans(root);
        while(!r.isEmpty()){
            TreeNode temp = (TreeNode)r.pop();
            l.add(temp.val);
        }
        return l;
    }
    public void trans(TreeNode root){
        while(root != null || !s.isEmpty()){
            while(root != null){
                s.add(root);
                r.add(root);
                root = root.right;
            }
            if(!s.isEmpty()){
                root = (TreeNode)s.pop();
                root = root.left;           
            }
        }
    }
}

层序遍历

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

class Solution {
    Queue<TreeNode> q;
    ArrayList<List<Integer>> r;
    ArrayList<Integer> temp;
    Solution(){
        q = new LinkedList<TreeNode>();
        temp = new ArrayList<Integer>();
        r = new  ArrayList<List<Integer>>();
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        int count = 0; //count为下一深度结点数量
        int cur = 1; //cur为当前深度剩余结点
        if(root == null)
            return r;
        q.add(root);
        while(!q.isEmpty()){
            cur--;
            root = q.remove();
            temp.add(root.val);          
            if(root.left != null){
                q.add(root.left);
                count++;
            }
            if(root.right != null){
                q.add(root.right);
                count++;
            }
            if(cur == 0){
                //当前深度遍历完毕
                //list中保存的是temp的引用，由于后续要清空list的内容，需要进行深复制        
                r.add((List<Integer>)temp.clone());   
                temp.clear();
                cur = count;
                count = 0;
            }
        }
        return r;
    }
}