二叉树遍历

1.遍历：前序、中序、后续、层序（前三种是深度遍历，后一种是广度遍历）

前序：根、左子树、右子树

中序：左子树、根、右子树

后序：左子树、右子树、根

（根访问的位置不同）

层序：一层一层 A B C D E NULL NULL NULL NULL NULL NULL

注意：如何判断是否为完全二叉树——看节点和空是否分离

2.实现——需要用到递归的方法

前序的遍历、节点数、叶子数实现

//遍历 vector<int> preorderTraversal(TreeNode* root) { vector<int> arr; if(!root) { arr.push_back(0); //把左右子节点的空也给出来了 return arr; } arr.push_back(root->val); vector<int> left=preorderTraversal(root->left); vector<int> right=preorderTraversal(root->right); arr.insert(arr.end(),left.begin(),left.end()); arr.insert(arr.end(),right.begin(),right.end()); return arr; } //求节点数 int treesize(TreeNode* root) { if(root==nullptr) return 0; else return 1+treesize(root->left)+treesize(root->right); } //求叶子数 int treeleafsize(TreeNode* root) { if(root==nullptr) return 0; if(root->left==nullptr&&root->right==nullptr) return 1; return treeleafsize(root->left)+treeleafsize(root->right); }

中序

class Solution { public: void inorder(TreeNode* root,vector<int> & res) { if(root==nullptr) return; inorder(root->left,res); res.push_back(root->val); inorder(root->right,res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; inorder(root,res); return res; } };

后序：

class Solution { public: void postorder(TreeNode* root,vector<int> & res) { if(root==nullptr) return; postorder(root->left,res); postorder(root->right,res); res.push_back(root->val); } vector<int> postorderTraversal(TreeNode* root) { vector<int> res; postorder(root,res); return res; } };