1.leetcode-104.二叉樹的最大深度

題目描述

給定一個二叉樹，找出其最大深度。二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
給定二叉樹 [3,9,20,null,null,15,7]，返回它的最大深度 3 。

遞歸方法

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

非遞歸方法

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int height=0;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int num_size = q.size();
            for(int i=0;i<num_size;i++){
                TreeNode *p = q.front();
                q.pop();
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
            }
            height++;
        }
        return height;
    }
};

2.leetcode-144.二叉樹的前序遍歷

題目描述

給定一個二叉樹，返回它的 前序 遍歷。

非遞歸方法

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            TreeNode *p=s.top();
            ans.push_back(p->val);
            s.pop();
            if(p->right) s.push(p->right);
            if(p->left) s.push(p->left);
        }
        return ans;
    }
};

3.leetcode-94.二叉樹的中序遍歷

題目描述

給定一個二叉樹，返回它的 中序 遍歷。

非遞歸方法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        stack<TreeNode*> s;
        TreeNode *cur=root;
        while(cur!=nullptr || !s.empty()){
            while(cur){
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            ans.push_back(cur->val);
            cur=cur->right;
        }
        return ans;
    }
};

4.leetcode-145.二叉樹的后序遍歷

題目描述

給定一個二叉樹，返回它的 后序 遍歷。

非遞歸方法

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        stack<TreeNode*> s;
        TreeNode* cur=root;
        TreeNode* last=nullptr;
        while(cur || !s.empty()){
            while(cur){
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            if(!cur->right || cur->right==last){
                ans.push_back(cur->val);
                s.pop();
                last=cur;
                cur=nullptr;
            }else cur=cur->right;
        }
        return ans;
    }
};