1. Binary Tree Preorder Traversal

Description

Given a binary tree, return the preorder traversal of its nodes' values.
Example:

Input: [1,null,2,3]
1

2
/
3

Output: [1,2,3]

Analysis

1. 实际就是二叉树的先序遍历，先序对应得是根节点的访问顺序。
2. leetcode上树节点的定义如下

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

3. 利用栈的思想，压入根节点，访问值，退栈，压入左右子节点，访问栈顶，退栈顶。直到栈为空。

Solution

// 使用栈记录访问过程中得节点指针，首先压栈根节点，访问该节点数据，后退栈，再将其右左节点压栈。
// 不断访问栈顶后后退栈顶，直到栈为空。
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode *> s;
        if(root!=nullptr)
            s.push(root);
        while(!s.empty())
        {
            TreeNode* p = s.top();
            result.push_back(p->val);
            s.pop();
            if(p->right!=nullptr)
                s.push(p->right);
            if(p->left!=nullptr)
                s.push(p->left);
        }
        return result;
    }
};

---

---

2.Binary Tree Inorder Traversal

Description

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

Example:

Input: [1,null,2,3]
1

2
/
3

Output: [1,3,2]

Analysis

1. 实际就是二叉树的中序遍历
2. 不断的压入根左左左左，直到没有左节点（即找到最左边的节点）。

Solution

// 从根节点开始不断压入根左左左左，直到没有左节点，访问。
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode *> s;
        TreeNode* p = root;
        while(!s.empty() || p!=nullptr)
        {
            if(p!=nullptr)
            {
                s.push(p);
                p = p->left;
            }
            else
            {
                // 最左边的节点
                p = s.top();
                s.pop();
                result.push_back(p->val);
                // 最关键
                p = p->right;
            }
        }
        return result;
        
    }
};

3.Binary Tree Postorder Traversal

Description

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

Example:

Input: [1,null,2,3]
1

2
/
3

Output: [3,2,1]

Analysis

1. 二叉树后序遍历
2. 此题有难度，需要考虑右子树的存在

Solution

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;
        TreeNode *p=root, *q = nullptr;
        do
        {
            // 不断往左下走
            while(p!=nullptr)
            {
                s.push(p);
                p = p->left;
            }
            q = nullptr;
            while(!s.empty())
            {
                p = s.top();
                s.pop();
                // 如果此时这个栈顶节点不存在右节点，或者已经被访问，则访问他
                if(p->right == q)
                {
                    result.push_back(p->val);
                    // 保存刚刚访问的节点
                    q = p;
                }
                // 否则的话，该节点还不能访问，重新进站，先访问其右子树
                else
                {
                    s.push(p);
                    p = p->right;
                    break;
                }
            }
        }while(!s.empty());
        return result;
    }
};

总结

1. 二叉树的三种遍历方式是二叉树算法的前提。
2. 二叉树三种遍历方法最简单的是用递归地方式，如下

// 先序
void preorder(TreeNode *root)
{
    if(root!=nullptr)
    {
        visit(root);
        preorder(root->left);
        preorder(root->right);
    }
}

// 中序
void inorder(TreeNode *root)
{
    if(root!=nullptr)
    {
        inorder(root->left);
        visit(root);
        inorder(root->right);
    }
}

// 后序
void postorder(TreeNode *root)
{
    if(root!=nullptr)
    {
        postorder(root->left);
        postorder(root->right);
        visit(root);
    }
}

3. 递归方式很简单，所以要学会使用栈或线索二叉树写这三种遍历。

---

---

4. Binary Tree Level Order Traversal

Description

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

Analysis

1. 二叉树的层序遍历，层序遍历是二叉树的广度优先搜索方式，先后中遍历都是二叉树的深度优先搜索方式。
2. 建立一个queue，然后先把根节点放进去，这时候找根节点的左右两个子节点，这时候去掉根节点，此时queue里的元素就是下一层的所有节点，用一个for循环遍历它们，然后存到一个一维向量里，遍历完之后再把这个一维向量存到二维向量里，以此类推，可以完成层序遍历。
3. 比较复杂的是需要将每层数分开

class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > res;
        if (root == NULL) return res;
        // 建立队列
        queue<TreeNode*> q;
        // 根节点先入队
        q.push(root);
        while (!q.empty()) {
            // 当前层值得容器
            vector<int> oneLevel;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode *node = q.front();
                q.pop();
                oneLevel.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(oneLevel);
        }
        return res;
    }
};

---

---

5. Same Tree

Description

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Analysis

1. 判断两个二叉树是否相同，必须树结构和相应得节点值都相同。
2. 树结构相同，就是比较是否一个这个地方有节点，一个这个地方无节点。
3. 采用递归得想法，分成三种情况： 如果两个位置都是空，则是相同，如果一个空一个非空，则不同，最后根节点，左子树，右子树三方判断合并。

Solution

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 如果两个树都是空，则是相同
        if(!p && !q)
            return true;
        // 如果一个空一个非空
        if(!p || !q)
            return false;
        // 根节点，左子树，右子树三方判断合并
        return (p->val==q->val) && (isSameTree(p->left, q->left)) 
        && (isSameTree(p->right, q->right));
    }
};

---

---

6. Symmetric Tree

Decription

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Analysis

1. 判断一棵树是否是对称的。思路和判断两棵树是否是相同的很类似。都是递归的思想，区别是，这里因为是一棵树，所以需要先考虑根节点。后面三方合并的地方，判断两棵树相同是同时递归做作，右右。判断一棵树是否对称，应该递归左右，右左。

Solution

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        else
            return isSymmetric(root->left, root->right);
    }
    
    bool isSymmetric(TreeNode *p, TreeNode *q)
    {
        if(!p && !q)
            return true;
        if(!p || !q)
            return false;
        return (p->val == q->val) && (isSymmetric(p->left, q->right)) 
        && (isSymmetric(p->right, q->left));
    }
};

---

---

7. Construct Binary Tree from Preorder and Inorder Traversal

Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Analysis

1. 根据先序遍历和中序遍历结果，建立二叉树
2. 先序的顺序的第一个肯定是根，所以原二叉树的根节点可以知道，题目中给了一个很关键的条件就是树中没有相同元素，有了这个条件我们就可以在中序遍历中也定位出根节点的位置，并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数。

Solution

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    TreeNode *buildTree(vector<int> &preorder, int pLeft, int pRight, vector<int> &inorder, int iLeft, int iRight) {
        if (pLeft > pRight || iLeft > iRight) return NULL;
        int i = 0;
        for (i = iLeft; i <= iRight; ++i) {
            if (preorder[pLeft] == inorder[i]) break;
        }
        TreeNode *cur = new TreeNode(preorder[pLeft]);
        cur->left = buildTree(preorder, pLeft + 1, pLeft + i - iLeft, inorder, iLeft, i - 1);
        cur->right = buildTree(preorder, pLeft + i - iLeft + 1, pRight, inorder, i + 1, iRight);
        return cur;
    }
};

8. Construct Binary Tree from Inorder and Postorder Traversal

Description

Given inorder and postorder traversal of a tree, construct the binary tree.

Analysis

1. 利用中序和后序遍历，建立二叉树
2. 中序的遍历顺序是左-根-右，后序的顺序是左-右-根，对于这种树的重建一般都是采用递归来做。由于后序的顺序的最后一个肯定是根，所以原二叉树的根节点可以知道，题目中给了一个很关键的条件就是树中没有相同元素，有了这个条件我们就可以在中序遍历中也定位出根节点的位置，并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数。

Solution

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
    TreeNode *buildTree(vector<int> &inorder, int iLeft, int iRight, vector<int> &postorder, int pLeft, int pRight) {
        if (iLeft > iRight || pLeft > pRight) return NULL;
        TreeNode *cur = new TreeNode(postorder[pRight]);
        int i = 0;
        for (i = iLeft; i < inorder.size(); ++i) {
            if (inorder[i] == cur->val) break;
        }
        cur->left = buildTree(inorder, iLeft, i - 1, postorder, pLeft, pLeft + i - iLeft - 1);
        cur->right = buildTree(inorder, i + 1, iRight, postorder, pLeft + i - iLeft, pRight - 1);
        return cur;
    }
};

总结

1. 二叉树是一种递归的数据结构，基本所有题目都可以考虑递归的思想。
2. 递归一定是DFS，二叉树的先序中序后序都可以看成是DFS。
3. 递归和迭代的区别

• 递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环
• 递归循环中，遇到满足终止条件的情况时逐层返回来结束。迭代则使用计数器结束循环。
• 递归就是在过程或函数里面调用自身;在使用递归时,必须有一个明确的递归结束条件,称为递归出口.
• 迭代是逐渐逼近，用新值覆盖旧值，直到满足条件后结束，不保存中间值，空间利用率高。递归是将一个问题分解为若干相对小一点的问题，遇到递归出口再原路返回，因此必须保存相关的中间值，这些中间值压入栈保存，问题规模较大时会占用大量内存。

---

---

9. Minimum Depth of Binary Tree

Description

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Analysis

1. 判断一棵树的最小深度，即最快找到叶子节点的深度。

递归，若为空树返回0；

若左子树为空，则返回右子树的最小深度+1；（加1是因为要加上根这一层，下同）

若右子树为空，则返回左子树的最小深度+1；

若左右子树均不为空，则取左、右子树最小深度的较小值，+1；

Solution

class Solution {
public:
    int minDepth(TreeNode* root) {
        // 直接递归，初始根节点是没有brother
        return minDepth(root, false);
    }
    
    int minDepth(TreeNode* p, bool hasbrother)
    {
        // 当前节点是空节点
        if(!p)
            return hasbrother?INT_MAX:0;
        // 递归
        // 分别考虑左右子树
        return 1+min(minDepth(p->left, p->right!=NULL), 
                    minDepth(p->right, p->left!=NULL));
        
    }
};

---

---

10. Maximum Depth of Binary Tree

Description

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Analysis

1. 不需要考虑其它，直接递归

Solution

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        else
            return 1+max(maxDepth(root->left), maxDepth(root->right));
        
    }
};