玩命加载中 . . .

94/144/145-二叉树的遍历


LeetCode 94. Binary Tree Inorder Traversal

LeetCode-94

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

method

中序遍历:左-根-右

  • 递归
void inorder(TreeNode* cur, vector<int>& ret) {
    if (cur == nullptr) return;
    inorder(cur->left, ret);
    ret.push_back(cur->val);
    inorder(cur->right, ret);
}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    inorder(root, ret);
    return ret;
}
  • 迭代
  1. 一直往左子树深度遍历,期间把元素插入栈中,直到空
    空的话说明到了无左子树的节点,开始弹出元素,同时查看是否有右节点
  2. 有右节点,返回步骤1
  3. 无右节点,继续弹出元素
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (!root) return ret;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        if (cur) {
            st.push(cur);
            cur = cur->left;
        }
        else {  // cur空,但栈里有元素,就要弹出
            cur = st.top();
            st.pop();
            ret.push_back(cur->val);
            cur = cur->right;
        }
    }
    return ret;
}

LeetCode 144. Binary Tree Preorder Traversal

LeetCode-144

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

method

前序遍历:根-左-右

  • 递归法
void preorder(TreeNode* cur, vector<int>& ret) {
    if (cur == nullptr) return;
    ret.push_back(cur->val);
    preorder(cur->left, ret);
    preorder(cur->right, ret);
}
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    preorder(root, ret);
    return ret;
}
  • 迭代法

先放右节点,再放左节点,待会取的时候就是先左再右

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (!root) return ret;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        ret.push_back(cur->val);
        if (cur->right) st.push(cur->right);
        if (cur->left) st.push(cur->left);
    }
    return ret;
}

LeetCode 145. Binary Tree Postorder Traversal

LeetCode-145

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

method

后序遍历:左-右-根

  • 递归法
void postorder(TreeNode* cur, vector<int>& ret) {
    if (cur == nullptr) return;
    postorder(cur->left, ret);
    postorder(cur->right, ret);
    ret.push_back(cur->val);
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    postOrder(root, ret);
    return ret;
}
  • 迭代法

后序左右根,反过来就是根右左,与先序遍历差不多,最后反转就可以了

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (root == nullptr) return ret;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        ret.push_back(cur->val);
        if (cur->left) st.push(cur->left);
        if (cur->right) st.push(cur->right);
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

文章作者: kunpeng
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 kunpeng !
  目录