树

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

题目描述

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
给定二叉树 [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;
    }
};