二叉樹的遍歷（遞歸）
144. 二叉樹的前序遍歷
難度簡單
1087
給你二叉樹的根節(jié)點?root?，返回它節(jié)點值的?前序?遍歷。
?
示例 1：
輸入：root = [1,null,2,3]輸出：[1,2,3]
示例 2：
輸入：root = []輸出：[]
示例 3：
輸入：root = [1]輸出：[1]
示例 4：
輸入：root = [1,2]輸出：[1,2]
示例 5：
輸入：root = [1,null,2]輸出：[1,2]
?
提示：
樹中節(jié)點數(shù)目在范圍?
[0, 100]?內(nèi)-100 <= Node.val <= 100
正確做法：
/**
?*?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?traversaltree(TreeNode?*cur,?vector<int>&?vec)
????{
????????if(cur==nullptr)return;
????????vec.push_back(cur->val);
????????traversaltree(cur->left,vec);
????????traversaltree(cur->right,vec);
????}
????vector<int>?preorderTraversal(TreeNode*?root)?{
????????vector<int>?ans;
????????traversaltree(root,?ans);
????????return?ans;
????}
};
注意：遞歸算法中的形參vector要傳引用，不然無法記錄
94. 二叉樹的中序遍歷
難度簡單
1862
給定一個二叉樹的根節(jié)點?root?，返回?它的?中序?遍歷?。
?
示例 1：
輸入：root = [1,null,2,3]輸出：[1,3,2]
示例 2：
輸入：root = []輸出：[]
示例 3：
輸入：root = [1]輸出：[1]
?
提示：
樹中節(jié)點數(shù)目在范圍?
[0, 100]?內(nèi)-100 <= Node.val <= 100
?
/**
?*?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?traversaltree(TreeNode?*cur,?vector<int>&?vec){
????????if(cur==nullptr)return;
????????traversaltree(cur->left,?vec);
????????vec.push_back(cur->val);
????????traversaltree(cur->right,?vec);
????}
????vector<int>?inorderTraversal(TreeNode*?root)?{
????????vector<int>?ans;
????????traversaltree(root,?ans);
????????return?ans;
????}
};
145. 二叉樹的后序遍歷
難度簡單
1057
給你一棵二叉樹的根節(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
?
進階：遞歸算法很簡單，你可以通過迭代算法完成嗎？
通過次數(shù)644,390提交次數(shù)844,674
/**
?*?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?traversaltree(TreeNode?*cur,?vector<int>&?vec){
????????if(cur==nullptr)return;
????????traversaltree(cur->left,?vec);
????????traversaltree(cur->right,?vec);
????????vec.push_back(cur->val);
????}
????vector<int>?postorderTraversal(TreeNode*?root)?{
????????vector<int>?ans;
????????traversaltree(root,?ans);
????????return?ans;
????}
};
