0094. Binary Tree Inorder Traversal.md

• 94/. Binary Tree Inorder Traversal.md
• 难度：Easy｜ 简单
• 相关知识点：Binary Tree
• 题目链接：
• https://leetcode.com/problems/binary-tree-inorder-traversal/description/

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

Example 1:

Input: root = [1,null,2,3] Output: [1,3,2] Example 2:

Input: root = [] Output: [] Example 3:

Input: root = [1] Output: [1]

Constraints:

The number of nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100

Solution 1 :nonrecursive【Depth-First-Search，DFS】

python版本

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:     
        stack = []
        ret = []
        r = root
    
        while stack or r:
            if r:
                stack.append(r)
                r = r.left
            else:
                r = stack.pop()
                ret.append(r.val)
                r = r.right
        
        return ret

c++版本

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> nodes;
        stack<TreeNode*> todo;
        while (root || !todo.empty()) {
            while (root) {
                todo.push(root);
                root = root -> left;
            }
            root = todo.top();
            todo.pop();
            nodes.push_back(root -> val);
            root = root -> right;
        }
        return nodes;
    }
};

Solution 2: 递归 Recursion

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ret = []
        stack = []
        if root:
            ret.extend(self.inorderTraversal(root.left))
            ret.append(root.val)
            ret.extend(self.inorderTraversal(root.right))
        return ret

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        l = []
        def inorder(node):
            if not node:
                return
            
            inorder(node.left)
            l.append(node.val)
            inorder(node.right)
        
        inorder(root)
        return l

### c++版本

/**

• 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: void traversal(TreeNode node, vector& res){ if (node == NULL) return; traversal(node->left, res); res.emplace_back(node->val); traversal(node->right, res); }

  vector inorderTraversal(TreeNode* root) { vector res; if(root == nullptr){ return res; } traversal(root, res); return res; } };

学习：

1. c++中pop 和python中pop的区别 c++中pop没有返回值，取栈顶元素需要

// 获取并移除栈顶元素
int topElement = myStack.top();
myStack.pop();

2. c++ 中push_back 和 emplace_back的区别 emplace_back 更适用于直接在容器中构造新元素，而 push_back 更适用于将已有元素的拷贝添加到容器中。

emplace_back

struct MyStruct {
    int x;
    MyStruct(int a) : x(a) {}
};

std::vector<MyStruct> myVector;
myVector.emplace_back(42); // 直接构造 MyStruct 对象，不需要额外的拷贝或移动

push_back

std::vector<int> myVector;
int value = 42;
myVector.push_back(value); // 添加 value 的拷贝