思想：

明确一个节点需要完成的工作，其他的工作是用框架找到节点

  1. void traverse(TreeNode* root)
  2. {
  3.     /*
  4.          root 的工作
  5.     */
  7.    // 框架工作                                                                                                                                                                                                                                                                                
  8.    traverse(root->left);
  9.    traverse(root->right);
  10. }

先来看两个小例子：

01 两个二叉树是否相等:

def isSame(root1, root2):
    #节点的工作:判断节点是否相等
    # 都为空相等 
    if not root1 and not root2 : return True
    if not root1 or not root2 : return False
    #框架工作 找到节点
    #递归找到左右子树所有节点
    return isSame(root1.left, root2.left) and \
            isSame(root1.right, root2.right)

这个例子改进下就是判断二叉树是否对称

bool isSymmetric(TreeNode* root)
{
    return isSame(root,root);
}
bool isSame(TreeNode* root1,TreeNode* root2)
{
    if (!root1 && !root2) return true;
    else if(!root1 || !root2) return false;
    return (root1->val == root2->val) && isSame(root1->left,root2->right) \
            && isSame(root1->right,root2->left);
}

再套用到下一题中

剑指 Offer 26. 树的子结构 MEDIUM

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B) return false;
       return isSame(A,B) || isSubStructure(A->left,B) ||  isSubStructure(A->right,B);
    }
    bool isSame(TreeNode* A,TreeNode* B)
    {
        if(!B) return true;// 这句必须在前面 先判断B有没有被遍历完
        if(!A) return false;

        return (A->val==B->val) && isSame(A->left,B->left) && isSame(A->right,B->right);

    }

};

02 二叉树所有节点加一

def plusOne(root):
    # 节点的工作 +1
    if not root: return 
    root.val += 1
    # 框架的工作 找到所有节点
    plusOne(root.left)
    plusOne(root.right)

然后看看树的常见操作—遍历
首先看看DFS和BFS.

1. DFS

DFS 说到底就是回溯的问题. 而解决一个回溯问题, 实际上就是一个**决策树的遍历**过程.
.

  1. 路径 ：已做出的选择
  2. 选择列表：当前可以做的选择
  3. 边界条件：决策树底层，无法做出选择的条件
res = []
def backtrack(...):
   if border condition:
       res.add(path)
       return 
   for select in selects_list:
       # make selection
       backtrack(...)
       # cancel selection

剑指 Offer 34. 二叉树中和为某一值的路径 MEDIUM

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树，以及目标和 sum = 22，

         5

        / \

       4   8

      /   / \

     11  13  4

    /  \    / \

   7    2  5   1

返回:

[

[5,4,11,2],

[5,8,4,5]

]

class Solution 
{
public:
    vector<vector<int>> res;
    vector<vector<int>>  pathSum(TreeNode* root, int sum)
    {
        if(!root) return {};
        vector<int> tmp;
        dfs(root, tmp, sum);
        return res;
    }
    void dfs(TreeNode* root, vector<int>& tmp, int sum)
    {
        if(root==nullptr) return;
        //边界
        else if (root->left == nullptr && root->right == nullptr && sum-root->val==0)
        {
            tmp.emplace_back(root->val);
            res.emplcae_back(tmp);
            tmp.pop_back();
            return;
        }
        // 做选择 回溯
        tmp.emplace_back(root->val);
        dfs(root->left, tmp, sum-root->val);
        dfs(root->right, tmp, sum-root->val);
        tmp.pop_back();
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

'''DFS回溯'''
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        def dfs(root,tmp,target):
            if not root:
                return
            tmp.append(root.val)

            if target == root.val and not root.left and not root.right:
                res.append(tmp.copy())
            dfs(root.left,tmp,target-root.val)
            dfs(root.right,tmp,target-root.val)
            tmp.pop()
        dfs(root,[],sum)
        return res
'''DFS迭代'''
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        if not root:return res
        stack = [(root,root.val,[root.val])]
        while stack:
            node,val,tmp = stack.pop()
            if val == sum and not node.left and not node.right:
                res.append(tmp)
            if node.left:
                stack.append((node.left,node.left.val+val,tmp+[node.left.val]))
            if node.right:
                stack.append((node.right,node.right.val+val,tmp+[node.right.val]))
        return res

'''BFS迭代'''

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:        
        if not root: return []
        queue = [(root, root.val, [root.val])]
        res = []
        while queue:
            node, val, temp = queue.pop(0)
            if val == sum and not node.left and not node.right: res.append(temp)
            if node.left:
                queue.append((node.left, val + node.left.val, temp+[node.left.val]))
            if node.right:
                queue.append((node.right, val + node.right.val , temp+[node.right.val]))
        return res

2. BFS

BFS相对于DFS最大的区别是:**BFS找到的路径一定是最短的, 但代价就是空间复杂度比DFS大了很多.**

BFS使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。BFS总共有两个模板：

如果不需要确定当前遍历到了哪一层，BFS模板如下。

while queue 不空：
   cur = queue.pop()
   for 节点 in cur的所有相邻节点：
       if 该节点有效且未访问过：
           queue.push(该节点)

如果要确定当前遍历到了哪一层，BFS模板如下。这里增加了level表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。


level = 0
while queue 不空：
   size = queue.size()
   while (size --) {
       cur = queue.pop()
       for 节点 in cur的所有相邻节点：
           if 该节点有效且未被访问过：
               queue.push(该节点)
  }
   level ++

剑指 Offer 55 - I. 二叉树的深度 EASY

迭代 层次

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root)
    {
        int res =0;
        if (!root) return res;
        queue<TreeNode*> que;
        que.emplace(root);
        while(!que.empty())
        {
            int n = que.size();
            for (int i =0;i<n;i++)
            {
                TreeNode *tmp = que.front();
                   que.pop();
                if (tmp->left) que.emplace(que->left);
                if (tmp->right) que.emplace(que->right);
            }
            res++;
        }
        return res;
    }
};

递归

class Solution {
public:
    int maxDepth(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        return (l>r?l:r)+1;
    }
};

Q1376. 通知所有员工所需的时间 MEDIUM

公司里有 n 名员工，每个员工的 ID 都是独一无二的，编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。 在 manager 数组中，每个员工都有一个直属负责人，其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人，manager[headID] = -1。题目保证从属关系可以用树结构显示。 公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。 第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属（也就是说在 informTime[i] 分钟后，他的所有直属下属都可以开始传播这一消息）。 返回通知所有员工这一紧急消息所需要的 分钟数 。 示例 1： 输入：n = 1, headID = 0, manager = [-1], informTime = [0] 输出：0 解释：公司总负责人是该公司的唯一一名员工。 示例 2： 输入：n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0] 输出：1 解释：id = 2 的员工是公司的总负责人，也是其他所有员工的直属负责人，他需要 1 分钟来通知所有员工。 上图显示了公司员工的树结构。 通过次数4,343 | 提交次数9,095

class Solution {
public:
        /*
            树的根到叶子的最长路径
        */
    vector<vector<int>> son;
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        son = vector<vector<int>>(n);
        for ( int i=0;i<n;i++)
        {
            if (i!=headID)
            {
                son[manager[i]].push_back(i);//son[i]为员工i的下级列表
            }
        }
        return dfs(headID,informTime);
    }

    int dfs(int cur,vector<int>& informTime)
    {
        int res=0;
        for(auto& s:son[cur])
        {
            res = max(res,dfs(s,informTime));
        }
        return res+informTime[cur];

    }
};

Q94. 二叉树的中序遍历 MEDIUM

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
'''递归'''
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res= []
        def inorder(root):
            if not root:
                return 
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(root)
        return res
'''非递归'''
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res,stack = [],[]
        p = root
        while p or stack:
            while p:
                stack.append(p)
                p = p.left

            q = stack.pop()
            res.append(q.val)
            p = q.right
        return res

Q102. 二叉树的层次遍历 MEDIUM

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 示例： 二叉树：[3,9,20,null,null,15,7], 3 / 9 20 /
15 7 返回其层次遍历结果： [ [3], [9,20], [15,7] ] 通过次数147,259 | 提交次数233,893

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
'''BFS'''
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        from collections import deque
        queue = deque()
        queue.append(root)
        res = []
        while queue:
            size = len(queue)
            level = []
            for _ in range(size):
                cur = queue.popleft()
                if not cur:
                    continue
                level.append(cur.val)
                queue.append(cur.left)
                queue.append(cur.right)
            if level:
                res.append(level)

        return res
'''DFS'''
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res = []
        def dfs(root,index):
            # res=[[1],[2,3]] index=3 插入空list存放第三层
            if len(res)<index:
                res.append([])
            # 第index层的索引是index-1
            res[index-1].append(root.val)
            if root.left:
                dfs(root.left,index+1)
            if root.right:
                dfs(root.right,index+1)

        dfs(root,1)
        return res

Q110. 平衡二叉树 EASY

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
''''自顶向下'''
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        if abs(self.height(root.left) - self.height(root.right))>1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

    def height(self,root):
        if  not root:
            return 0
        return max(self.height(root.right),self.height(root.left))+1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
'''自底向上'''
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.recur(root) != -1

    def recur(self,root):
        if not root:
            return 0
        left = self.recur(root.left)
        if left == -1:
            return -1
        right = self.recur(root.right)
        if right == -1:
            return -1
        return max(left,right) + 1 if abs(left - right) < 2 else -1

235. 二叉搜索树的最近公共祖先 EASY

利用二叉搜索树的特点， 如果p、q的值都小于root，说明p q 肯定在root的左子树中； 如果p q都大于root，说明肯定在root的右子树中， 如果一个在左一个在右 则说明此时的root记为对应的最近公共祖先

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

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

236. 二叉树的最近公共祖先 MEDIUM

class Solution
{
      /*
        左子树含有p或者q，返回p,q（root == q || root == p时返回root）
        右子树含有p或者q，返回p,q（root == q || root == p时返回root）
        1. 左右子返回的root都不是空说明p, q一个左一个右
        2. 左返回不空 右返回空 说明p, q都在左边
        3. 右返回不空 左返回空 说明p, q都在右边

    */
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 1 如果root空 表明此时p,q都不在此子树中 返回空
        // 1 如果root==p 表明此时p在此子树中 返回p 非空
        // 1 如果root==q 表明此时q在此子树中 返回q 非空
        if (!root || root==p || root==q) return root;
        TreeNode* l = lowestCommonAncestor(root->left,p,q);
        TreeNode* r = lowestCommonAncestor(root->right,p,q);
        // 1. 一个左一个右
        if (l && r) return root;
        // 2. 都在左
        else if (l) return l;
        // 3. 都在右
        else if (r) return r;
        else return NULL;
    }
};

Q144. 二叉树的前序遍历 MEDIUM

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
'''递归'''
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def pre(root):
            if not root:
                return
            res.append(root.val)
            pre(root.left)
            pre(root.right)
        pre(root)
        return res
'''非递归'''
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = [] 
        stack = []
        p = root
        while p or stack:
            while p:
                res.append(p.val)
                stack.append(p)
                p = p.left
            q = stack.pop()
            p = q.right
        return res

Q145. 二叉树的后序遍历 HARD

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
''''递归'''
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def post(root):
            if not root:
                return
            post(root.left)
            post(root.right)
            res.append(root.val)

        post(root)
        return res
'''非递归'''

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root
        while stack or cur:
            while cur:
                res.append(cur.val)
                stack.append(cur)
                cur = cur.right  #先将右节点压栈
            top = stack.pop()  #此时该节点的右子树已经全部遍历完
            cur = top.left  #对左子树遍历
        return res[::-1]  #结果翻转

199. 二叉树的右视图 MEDIUM

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释: 1 <—- /
2 3 <—- \
5 4 <—- 通过次数50,226 | 提交次数78,779

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        '''
            层次遍历的每层最右非空节点
        '''
        res = []
        from collections import deque
        queue = deque()
        queue.append(root)
        while queue:
            size = len(queue)
            index = size
            for i in range(size):
                cur = queue.popleft()
                index-=1
                if not cur:
                    continue
                if not index:
                    res.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:    
                    queue.append(cur.right)
        return res

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None

        root = TreeNode(preorder[0]) # 先序 根左右 根据pre确定root
        r_index = inorder.index(preorder[0])    # 中序 左根右 根据root可以划分出左右子树

        root.left = self.buildTree(preorder[1:r_index+1],inorder[:r_index])
        root.right = self.buildTree(preorder[r_index+1:], inorder[r_index + 1:])
        return root

106. 从中序与后序遍历序列构造二叉树 MEDIUM

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not postorder:
            return None
        root = TreeNode(postorder[-1])
        r_index = inorder.index(root.val)

        root.left = self.buildTree(inorder[:r_index],postorder[:r_index])
        root.right = self.buildTree(inorder[r_index+1:],postorder[r_index:-1])
        return root

面试题 04.03. 特定深度节点链表 MEDIUM

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。 示例： 输入：[1,2,3,4,5,null,7,8]

       1
       /  \ 
      2    3
     / \    \ 
    4   5    7
  /
 8

输出：[[1],[2,3],[4,5,7],[8]] 通过次数4,417 | 提交次数5,465

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
        ''''建链表'''
        def link(temp):
            ans = ListNode(temp[0])
            p=ans
            for i in temp[1:]:
                p.next = ListNode(i)
                p = p.next
            return ans


        if not tree:
            return []
        res = []
        from collections import deque
        level =deque()
        level.append(tree)
        while level:
            size = len(level)
            temp = []
            for i in range(size):
                cur = level.popleft()
                if not cur:
                    continue
                temp.append(cur.val)
                if cur.left:
                    level.append(cur.left)
                if cur.right:
                    level.append(cur.right)
            res.append(link(temp))
        return resz

剑指 Offer 13. 机器人的运动范围 MEDIUM