day14 | 二叉樹1

0.引言

● 理論基礎(chǔ)
● 遞歸遍歷
● 迭代遍歷
● 統(tǒng)一迭代

1.二叉樹基礎(chǔ)

2. 二叉樹的前序遍歷

Category Difficulty Likes Dislikes
algorithms Easy (71.33%) 1023 -

給你二叉樹的根節(jié)點 root ，返回它節(jié)點值的 前序遍歷。

示例 1：

image.png
輸入：root = [1,null,2,3]
輸出：[1,2,3]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

示例 4：

image.png
輸入：root = [1,2]
輸出：[1,2]

示例 5：

image.png
輸入：root = [1,null,2]
輸出：[1,2]

提示：

  • 樹中節(jié)點數(shù)目在范圍 [0, 100] 內(nèi)
  • -100 <= Node.val <= 100

進階：遞歸算法很簡單，你可以通過迭代算法完成嗎？

Discussion | Solution

2.1.遞歸法

/*
 * @lc app=leetcode.cn id=144 lang=cpp
 *
 * [144] 二叉樹的前序遍歷
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  vector<int> preorderTraversal(TreeNode* root) {
    std::vector<int> res;
    dfs(root, res);
    return res;
  }

 private:
  void dfs(TreeNode* node, std::vector<int>& res) {
    if (node == nullptr) {
      return;
    }
    res.push_back(node->val);
    dfs(node->left, res);
    dfs(node->right, res);
  }
};
// @lc code=end

2.2.迭代法

/*
 * @lc app=leetcode.cn id=144 lang=cpp
 *
 * [144] 二叉樹的前序遍歷
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  vector<int> preorderTraversal(TreeNode* root) {
    std::stack<TreeNode*> node_stack;
    std::vector<int> res;
    if (root == nullptr) return res;
    node_stack.push(root);
    while (!node_stack.empty()) {
      TreeNode* curr_node = node_stack.top();
      node_stack.pop();
      res.push_back(curr_node->val);
      // 右子節(jié)點先入棧，等會兒后出棧
      if (curr_node->right) node_stack.push(curr_node->right);
      if (curr_node->left) node_stack.push(curr_node->left);
    }
    return res;
  }
};
// @lc code=end

3. 二叉樹的中序遍歷

Category Difficulty Likes Dislikes
algorithms Easy (76.23%) 1736 -

給定一個二叉樹的根節(jié)點 root ，返回 它的 中序 遍歷 。

示例 1：

image.png
輸入：root = [1,null,2,3]
輸出：[1,3,2]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

提示：

  • 樹中節(jié)點數(shù)目在范圍 [0, 100] 內(nèi)
  • -100 <= Node.val <= 100

進階: 遞歸算法很簡單，你可以通過迭代算法完成嗎？

Discussion | Solution

3.1.遞歸法

/*
 * @lc app=leetcode.cn id=94 lang=cpp
 *
 * [94] 二叉樹的中序遍歷
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> res;
    dfs(root, res);
    return res;
  }

 private:
  void dfs(TreeNode* node, std::vector<int>& res) {
    if (node == nullptr) {
      return;
    }
    dfs(node->left, res);
    res.push_back(node->val);
    dfs(node->right, res);
  }
};
// @lc code=end

3.2.迭代法

  • 由于訪問順序和處理順序不一致
  • 1.借用指針遍歷訪問節(jié)點；2.使用棧性質(zhì)進行處理
/*
 * @lc app=leetcode.cn id=94 lang=cpp
 *
 * [94] 二叉樹的中序遍歷
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> node_stack;
    // 借用指針進行節(jié)點訪問
    TreeNode* cur = root;

    while (cur != nullptr || !node_stack.empty()) {
      // 深入到“最左”
      if (cur != nullptr) {
        node_stack.push(cur);
        cur = cur->left;
      } else {
        cur = node_stack.top();
        node_stack.pop();
        res.push_back(cur->val); 
        cur = cur->right;
      }
    }
    return res;
  }
};
// @lc code=end

4. 二叉樹的后序遍歷

Category Difficulty Likes Dislikes
algorithms Easy (76.31%) 1006 -

給你一棵二叉樹的根節(jié)點 root ，返回其節(jié)點值的 **后序遍歷 **。

示例 1：

輸入：root = [1,null,2,3]
輸出：[3,2,1]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

提示：

  • 樹中節(jié)點的數(shù)目在范圍 [0, 100] 內(nèi)
  • -100 <= Node.val <= 100

進階：遞歸算法很簡單，你可以通過迭代算法完成嗎？

Discussion | Solution

4.1.遞歸法

/*
 * @lc app=leetcode.cn id=145 lang=cpp
 *
 * [145] 二叉樹的后序遍歷
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  vector<int> postorderTraversal(TreeNode* root) {
    std::vector<int> res;
    dfs(root, res);
    return res;
  }

 private:
  void dfs(TreeNode* node, std::vector<int>& res) {
    if (node == nullptr) {
      return;
    }
    dfs(node->left, res);
    dfs(node->right, res);
    res.push_back(node->val);
  }
};
// @lc code=end

4.2.迭代法

/*
 * @lc app=leetcode.cn id=145 lang=cpp
 *
 * [145] 二叉樹的后序遍歷
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  vector<int> postorderTraversal(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> node_stack;
    if (root == nullptr) return res;
    node_stack.push(root);
    while (!node_stack.empty()) {
      TreeNode* cur = node_stack.top();
      node_stack.pop();
      res.push_back(cur->val);
      // 先入左
      if (cur->left) node_stack.push(cur->left);
      if (cur->right) node_stack.push(cur->right);
    }
    std::reverse(res.begin(), res.end());
    return res;
  }
};
// @lc code=end

5. 二叉樹的層序遍歷

Category Difficulty Likes Dislikes
algorithms Medium (65.44%) 1612 -

給你二叉樹的根節(jié)點 root ，返回其節(jié)點值的 層序遍歷 。 （即逐層地，從左到右訪問所有節(jié)點）。

示例 1：

image.png
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]

示例 2：

輸入：root = [1]
輸出：[[1]]

示例 3：

輸入：root = []
輸出：[]

提示：

  • 樹中節(jié)點數(shù)目在范圍 [0, 2000] 內(nèi)
  • -1000 <= Node.val <= 1000

Discussion | Solution

5.1.遞歸法

/*
 * @lc app=leetcode.cn id=102 lang=cpp
 *
 * [102] 二叉樹的層序遍歷
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> res;
    dfs(root, 1, res);
    return res;
  }

 private:
  void dfs(TreeNode* node, int depth, std::vector<std::vector<int>>& res) {
    if (node == nullptr) {
      return;
    }
    if (res.size() < depth) {
      res.push_back(std::vector<int>());
    }
    res[depth - 1].push_back(node->val);
    dfs(node->left, depth + 1, res);   // depth隱式回溯
    dfs(node->right, depth + 1, res);  // depth隱式回溯
  }
};
// @lc code=end

5.2.迭代法

用 queue

/*
 * @lc app=leetcode.cn id=102 lang=cpp
 *
 * [102] 二叉樹的層序遍歷
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    if (root == nullptr) return {};

    std::vector<std::vector<int>> res;
    std::queue<TreeNode*> que;
    que.push(root);

    while (!que.empty()) {
      std::vector<int> one_level;
      // int que_size = que,size();
      // for (int i = 0; i < que_size; ++i) {
      // 這里的size是關(guān)鍵，size剛好是每層的節(jié)點數(shù)
      for (int i = que.size(); i > 0; --i) {
        TreeNode* cur = que.front();
        que.pop();
        one_level.push_back(cur->val);

        if (cur->left) que.push(cur->left);
        if (cur->right) que.push(cur->right);
      }
      res.push_back(one_level);
    }
    return res;
  }
};
// @lc code=end
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容