二叉树

树深度和高度

1. 树的高度和深度是一样的
2. 节点的深度和高度可能不一样
3. 深度是从上到下数的，而高度是从下往上数
4. 最大深度和最小深度（由题意而定）

二叉树遍历

前中后序遍历

前中后序遍历指的是中间节点的位置是在前还是中还是后

//前序遍历
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

层次遍历

1. 层次遍历使用队列这种数据结构
2. 要用 while 循环入队出队
3. if (root == NULL) return a;
   • 防止后续错误操作了为空的序列而报错
   • 剪枝，减少算法复杂度

/**
 * 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:
    queue<TreeNode*> q;
    vector<vector<int>> a; 
    vector<vector<int>> levelOrder(TreeNode* root) { 
        if (root == NULL) return a; //如果树为空就直接返回
        q.push(root);
        a.push_back({q.front()->val});
        //注意这里要用while
        while(!q.empty()){
            vector<int> b;
            int size = q.size(); //要遍历完当前整个队列的元素
            for(int i=0;i<size;i++){
                TreeNode* t = q.front();
                q.pop();
                if(t->left != NULL){
                    q.push(t->left);
                    b.push_back(t->left->val);
                }
                if(t->right != NULL){
                    q.push(t->right);
                    b.push_back(t->right->val);
                }
            }
            if(b.size() > 0) a.push_back(b);
        }
        return a;
    }
};

树的叶子节点路径

1. 定义的是string path，每次都是复制赋值，不用使用引用，否则就无法做到回溯的效果
2. 这里并没有加上引用& ，即本层递归中，path + 该节点数值，但该层递归结束，上一层path的数值并不会受到任何影响

lass Solution {
public:
//定义的是string path，每次都是复制赋值，不用使用引用，否则就无法做到回溯的效果
//这里并没有加上引用& ，即本层递归中，path + 该节点数值，但该层递归结束，上一层path的数值并不会受到任何影响
    void findPath(TreeNode* cur,string path,vector<string>& result){
        path += to_string(cur->val);
        if(cur->left == NULL && cur->right == NULL){
            result.push_back(path);
            return;
        }
        else{
            if(cur->left != NULL){
                path += "->";
                findPath(cur->left,path,result);
                path.pop_back(); //回溯'>'
                path.pop_back(); //回溯'-'
            }
            if(cur->right != NULL){
                path += "->";
                findPath(cur->right,path,result);
                path.pop_back(); //回溯'>'
                path.pop_back(); //回溯'-'
            }
        }

    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if(root == NULL) return result;
        findPath(root,path,result);
        return result;
    }
};

从前序与中序遍历序列构造二叉树

tips:

1. 对前序和中序进行分割
   • 前序是直接分割
   • 中序中间会空一个根节点进行分割
2. 对分割之后的左前序和左中序 以及 右前序和右中序 进行递归操作 分别得到当前根节点的左子节点和右子节点

class Solution {
public:
    TreeNode* createTree(vector<int>& preorder, vector<int>& inorder){
        if(preorder.size() == 0) return NULL;
        TreeNode* root = new TreeNode(preorder[0]);
        int inorderIndex = 0;
        int n = inorder.size();
        for(int i=0;i<n;i++){
            if(root->val == inorder[i]) inorderIndex = i;
        }
        //切割中序数组，两端切割出来的数组中间会空一个根节点
        // 左闭右开区间：[0, delimiterIndex)
        vector<int> leftinorder(inorder.begin(),inorder.begin()+inorderIndex);
        // [delimiterIndex + 1, end)
        vector<int> rightinorder(inorder.begin()+inorderIndex+1,inorder.end());

        preorder.erase(preorder.begin(),preorder.begin()+1);

        // 依然左闭右开，注意这里使用了左中序数组大小作为切割点
        // [0, leftInorder.size)
        vector<int> leftpreorder(preorder.begin(),preorder.begin()+leftinorder.size());
        // [leftInorder.size(), end)
        vector<int> rightpreorder(preorder.begin()+leftinorder.size(),preorder.end()); 

        root->left = createTree(leftpreorder,leftinorder);
        root->right = createTree(rightpreorder,rightinorder);

        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* root = createTree(preorder,inorder);
        return root;
    }
};