二叉树

一、目录

DFS

• 144.二叉树的前序遍历
• 145.二叉树的后序遍历（hard）
• 104.二叉树的最大深度
• 111.二叉树的最小深度
• 100.相同的树
• 226.翻转二叉树
• 112.路径总和
• 257.二叉树的所有路径

• 437.路径总和 III
• 剑指 Offer 26. 树的子结构

• 543.二叉树的直径
• 110.平衡二叉树
• 剑指 Offer 68 - II 二叉树的最近公共祖先
• 105. 从前序与中序遍历序列构造二叉树

BFS

• 102.二叉树的层序遍历
• 111.二叉树的最小深度
• 199.二叉树的右视图
• 103.二叉树的锯齿形层次遍历

二叉搜索树

• 二叉搜索树的第k大节点
• 判断数组是不是二叉搜索树的后序遍历结果
• 将二叉搜索树转换为双向链表

二、题目

144.二叉树的前序遍历

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    while (root || !s.empty()) {
        if (root) {
            s.push(root);
            res.push_back(root->val);
            root = root->left;
        }else{
            root = s.top(); s.pop();
            root = root->right;
        }
    }
    return res;
}

145.二叉树的后序遍历

思路：需要用到两个栈。

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if(!root) return res;

    stack<TreeNode*> s1;
    stack<TreeNode*> s2;
    // 中左右
    while (root || !s1.empty()) {
        if (root) {
            s1.push(root);
            s2.push(root);
            root = root->right;
        }else{
            root = s1.top(); s1.pop();
            root = root->left;
        }
    }
    // 左右中
    while (!s2.empty()) {
        res.push_back(s2.top()->val); s2.pop();
    }
    return res;
}

104.二叉树的最大深度

int maxDepth(TreeNode* root) {
    if (!root) return 0;

    int a = maxDepth(root->left);
    int b = maxDepth(root->right);
    
    return max(a, b) + 1;
}

111.二叉树的最小深度

考虑[1,2]这种情况

int minDepth(TreeNode* root) {
    if (!root) return 0;
    
    int a = minDepth(root->left);
    int b = minDepth(root->right);
    
    if (a==0 || b==0) return a + b + 1;
    
    return min(a, b) + 1;
}

100.相同的树

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    if (p->val != q->val) return false;
    
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

226.翻转二叉树

思路1：创建新二叉树

TreeNode* invertTree(TreeNode* root) {
    if (!root) return NULL;
    
    TreeNode* node = new TreeNode(root->val);
    
    node->left = invertTree(root->right);
    node->right = invertTree(root->left);
    
    return node;
}

思路2：原地改变二叉树
注意：返回值也可以不管，不要因此而影响思路；当然也可以另外写一个函数去执行逻辑。

TreeNode* invertTree(TreeNode* root) {
    if (!root) return NULL;
    
    swap(root->left, root->right);
    
    invertTree3(root->right);
    invertTree3(root->left);
    
    return root;
}

112.路径总和

题目描述：从根节点到叶子节点的路径的和等于sum

bool hasPathSum(TreeNode* root, int sum) {
    if (!root) return false;
    
    sum -= root->val;
    
    if (!root->left && !root->right){
        return sum==0;
    }
    return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
}

257.二叉树的所有路径

void dfs(TreeNode* node, string path, vector<string>& ans){
    path += to_string(node->val);
    
    if (!node->left && !node->right) {
        ans.push_back(path);
    }else{
        path += "->";
        if (node->left) dfs(node->left, path, ans);
        if (node->right) dfs(node->right, path, ans);
    }
}

vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> ans;
    if (!root) return ans;
    string path;
    dfs(root, path, ans);
    return ans;
}

437.路径总和 III

题目描述：找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的.

思路：双层dfs。

int count = 0;
// 遍历以该结点为首的树
void dfs2(TreeNode* node, int sum){
    if (!node) return;
    
    sum -= node->val;
    if (sum == 0) {
        count++;
    }
    dfs2(node->left, sum);
    dfs2(node->right, sum);
    
}
// 遍历整个树
void dfs(TreeNode* node, int sum){
    if (!node) return;
    
    dfs2(node, sum);
    dfs(node->left, sum);
    dfs(node->right, sum);
}

int pathSum(TreeNode* root, int sum) {
    dfs2(root, sum);
    return count;
}

剑指 Offer 26. 树的子结构

bool helper(Node* node1, Node* node2){
    if (!node2) return true;
    if (!node1) return false;
    if (node1->val != node2->val) return false;
    return helper(node1->left, node2->left) && helper(node1->right, node2->right);
}

bool isSubStructure(struct TreeNode* A, struct TreeNode* B){
    if (!A || !B) return false;
    
    if (helper(A, B)) return true;
    return isSubStructure(A->left, B) || isSubStructure(A->right, B);
}

543.二叉树的直径

思路：在求最大深度的DFS过程中判断。

int maxDepth = 0;
int helper(TreeNode* node){
    if (!node) return 0;
    
    int a = helper(node->left);
    int b = helper(node->right);
    maxDepth = max(a+b , maxDepth);
    return max(a, b) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    helper(root);
    return maxDepth;
}

110.平衡二叉树

思路：在求最大深度的DFS过程中判断。

int helper(TreeNode* root){
    if(!root) return 0;
    
    int left = helper(root->left);
    int right = helper(root->right);
    
    if (abs(left - right) > 1 || left == -1 || right == -1) {
        return -1;
    }
    return max(left, right) + 1;
}

bool isBalanced(TreeNode* root) {
    return helper(root) != -1;
}

剑指 Offer 68 - II 二叉树的最近公共祖先

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return NULL;
    if (root==p || root==q) return root;
    
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
    if (left && right) return root;
    if (left) return left;
    if (right) return right;
    
    return NULL;
}

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

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    if (inorderSize < 1) return NULL;

    int rootVal = postorder[postorderSize-1];
    Node* root = (Node*)malloc(sizeof(Node));
    root->val = rootVal;
    
    // 左子树的长度
    int leftLens = 0;
    while (inorder[leftLens] != rootVal) leftLens++;
    
    // 右子树的长度
    int rightLens = inorderSize - leftLens - 1;
    
    root->left =  buildTree(inorder, leftLens, postorder, leftLens);
    root->right = buildTree(inorder+leftLens+1, rightLens, postorder+leftLens, rightLens);
    return root;
}

102.二叉树的层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if(!root) return res;
    
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        vector<int> temp;
        int lens = q.size();
        for(int i=0; i<lens; i++){
            TreeNode* node = q.front(); q.pop();
            temp.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(temp);
    }
    return res;
}

111.二叉树的最小深度

199.二叉树的右视图

vector<int> rightSideView(TreeNode* root) {
    vector<int> ans;
    if (!root) return ans;
    
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
        int size = que.size();
        for (int i=0; i<size; i++) {
            TreeNode* node = que.front(); que.pop();
            
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
            if (i == size-1) {
                ans.push_back(node->val);
            }
        }
    }
    return ans;
}

103.二叉树的锯齿形层次遍历

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    if (!root) return ret;
    
    queue<TreeNode*> que;
    que.push(root);
    int col = 0;
    while (!que.empty()) {
        col++;
        int size = que.size();
        vector<int> temp;
        stack<int> st;
        while (size--) {
            TreeNode* node = que.front(); que.pop();
            
            if (col % 2 == 0) {
                st.push(node->val);
            }else{
                temp.push_back(node->val);
            }
            
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        while (!st.empty()) {
            temp.push_back(st.top()); st.pop();
        }

        ret.push_back(temp);
    }
    return ret;
}

二叉搜索树的第k大节点

思路：右根左DFS

void visit(struct TreeNode* root, int* k, int* ret){
    if (!root || *k <0) return;
    
    visit(root->right, k, ret);
    (*k)--;
    if (*k == 0) {
        *ret = root->val;
        return;
    }
    visit(root->left, k, ret);
}

int kthLargest(struct TreeNode* root, int k){
    int ret = 0;
    visit(root, &k, &ret);
    return ret;
}

判断数组是不是二叉搜索树的后序遍历结果

bool verifyPostorder(int* postorder, int lens){
    if (lens<=1) return true;
    
    int rootVal = postorder[lens-1];
    
    int leftLens = 0;
    while (postorder[leftLens]<rootVal) leftLens++;
    
    for (int i=leftLens; i<lens-1; i++) {
        if (postorder[i] < rootVal) {
            return false;
        }
    }
    return verifyPostorder(postorder, leftLens) && verifyPostorder(postorder+leftLens, lens-leftLens-1);
}

将二叉搜索树转换为双向链表

class Solution {
public:
    Node *head, *pre;
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        head = nullptr;
        dfs(root);
        head->left = pre, pre->right = head;
        return head;
    }

    void dfs(Node* root) {
        if (!root) return;
        dfs(root->left);
        if (!head) head = root, pre = root;
        else pre->right = root, root->left = pre, pre = root;
        dfs(root->right);
    }
};