1. 前序遍历

非递归写法：

  1. class Solution {
  2. public:
  3.     vector<int> preorderTraversal(TreeNode* root) {
  4.         if(root == nullptr) {
  5.           return;
  6.         }
  7.         TreeNode* node = root;
  8.         vector<int> list;
  9.         stack<TreeNode*> stk;
  10.         while(true) {
  11.           if(node != nullptr) {
  12.             // 访问当前节点
  13.             // 右节点入栈
  14.             // 往左走
  15.             list.push_back(root -> val);
  16.             if(node -> right != nullptr) {
  17.               stk.push(node -> right);
  18.             }
  19.             node = node -> left;
  20.           } else if(stk.size() == 0) {
  21.             break;
  22.           } else {
  23.             // 不能再往左了，去访问右节点(后遇到的右节点先访问，有点像栈，所以采用栈管理右节点)
  24.             node = stk.pop();
  25.           }
  26.         }
  27.        return list;
  28.     }
  29. };
  31. // 方法二
  32. vector<int> preorderTraversal(TreeNode* root) {
  33.   if(root == nullptr) {
  34.     return;
  35.   }
  36.   vector<int> list;
  37.   stack<TreeNode*> stk;
  38.   stk.push(root);
  39.   while(stk.size() != 0) {
  40.     TreeNode* node = stk.pop();
  41.     list.push_back(node -> val);
  42.     if(node -> right !=  nullptr) {
  43.       stk.push(node -> right);
  44.     }
  45.     if(node -> left != nullptr) {
  46.       stk.push(node -> left);
  47.     }
  48.   }
  49.   return list;
  50. }

递归写法：

class Solution {
public:
    vector<int> ret;
    void preOrder(TreeNode* root) {
        if(root != nullptr) {
            ret.push_back(root -> val);
            preOrder(root -> left);
            preOrder(root -> right);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        preOrder(root);
        return ret;
    }
};

2. 中序遍历

非递归写法：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {

        stack<TreeNode*> s;
        vector<int> ret;
        TreeNode* node = root;

        while(node != nullptr || !s.empty()) {
            while(node != nullptr) {
                s.push(node);
                node = node -> left;
            }
            node = s.top();
            s.pop();
            ret.push_back(node -> val);
            node = node -> right;    
        }
        return ret;
    }
};

// MJ
void inorder(TreeNode* root) {
  if(root == nullptr) {
    return;
  }
  TreeNode* node = root;
  stack<TreeNode*> s;
  while(true) {
    if(node != nullptr) {
      s.push(node);
      node = node -> left;
    } else if(s.size() == 0) {
      return;
    } else {
      node = s.pop();
      cout << node -> val << endl;
      node = node -> right;
    }
  }
}

递归写法：

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

3. 后序遍历

非递归写法：

class Solution {
public:

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        // auto it = ret.begin();
        stack<TreeNode*> s;
        if(root != nullptr) {
            s.push(root);
        }
        while(!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            ret.insert(ret.begin(), node -> val);
            // 先进栈左子树后右子树
            // 出栈的顺序就变更为先右后左
            // 右先头插法入list
            // 左再头插法入list
            // 实现右左根=>左右根
            if(node -> left) {
                s.push(node -> left);
            }
            if(node -> right) {
                s.push(node -> right);
            }
        }
        return ret;
    }
};

// MJ
void postorder(TreeNode* root) {
  if(root == nullptr) {
    return;
  }
  TreeNode* prev = null;
  stack<TreeNode*> stk;
  stk.push(root);
  while(stk.size() != 0) {
    TreeNode* top = stk.top();
    if((top -> left == nullptr && top -> right == nullptr) || (prev != null && prev -> parent == top)) {
      prev = stk.pop();
      cout << prev -> val << endl;
    } else {
      if(top -> right != nullptr) {
        stk.push(top -> right);
      }
      if(top -> left != nullptr) {
        stk.push(top -> left);
      }
    }
  }
}

递归写法：

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

4. 层序遍历 (要会默写)

简易思路：

if(root == nullptr) return;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
    TreeNode* node = q.front(); // 取出第一个
    q.pop(); // C++ 的 pop 函数不会返回取出的那个元素，只能取之先保存，这不方便
    cout << node -> val << endl;
    if(node -> left) {
        q.push(node -> left);
    }
    if(node -> right) {
        q.push(node -> right);
    }
}

非递归写法：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(root == nullptr) {
            return ret;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            auto size = q.size();
            // tmp 保存每一层的数据
            vector<int> tmp;
            for(int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                tmp.push_back(node -> val);
                if (node -> left) {
                    q.push(node -> left);
                }
                if (node -> right) {
                    q.push(node -> right);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

5. 二叉树的高度(利用层序遍历)

非递归写法：

int height(TreeNode* root) {
  if(root == nullptr) return 0;
  int height = 0;
  int levelSize = 1;  // 每一层的元素
  queue<TreeNode*> q;
  q.push(root);
  while(!q.empty()) {
    TreeNode* node = q.front();
    q.pop();
    levelSize--;
    if(node -> left) {
        q.push(node -> left);
    }
    if(node -> right) {
        q.push(node -> right);
    }
    if(levelSize == 0) {  // 即将要访问下一层
      levelSize = q.size();
      height++;
    }
  }
  return height;
}

递归写法：

int height(TreeNode* root) {
  if(root == nullptr) {
    return 0;
  }
  return 1 + max(height(root -> left), height(root -> right));
}

6. 判断完全二叉树(利用层序遍历)

从根往下数，除了最下层外都是全满（都有两个子节点），而最下层所有叶结点都向左边靠拢填满，构造一颗完全二叉树就是【从上到下，从左往右】的放置节点（即层序遍历）
42676-0955fabfb52c11db.webp

  1. 如果树为空，返回false
  2. 如果树不为空，开始层序遍历二叉树（用队列）
    • 如果node.left!=null,将node.left入队
    • 如果node.left== null && node.right != null, 返回 false
    • 如果node.right != null,将node.right入队
    • 如果node.right == null,那么后面遍历应该都为叶子结点，才是完全二叉树，否则返回false

  3. 遍历结束，返回true

    bool isComplete(TreeeNode* root) {
if(root == nullptr) return false;
queue<TreeNode*> q;
q.push(root);
bool leaf = false;
while(!q.empty()) {
 TreeNode* node = q.front();
 q.pop();

 if(leaf && !(node -> left == nullptr && node -> right == nullptr)) {
   return false;
 }

 if(node -> left) {
     q.push(node -> left);
 } else if(node -> right){
     // node.left == null && node.right != null
     return false;
 }

 if(node -> right) {
     q.push(node -> right);
 } else {
     // node.left == null && node.right == null
     // node.right != null && node.right == null
     leaf = true;
 }
}
return true;
}

7. 翻转二叉树

前序遍历：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) {
            return root;
        }
        TreeNode* tmp = root -> left;
        root -> left = root -> right;
        root -> right = tmp;
        invertTree(root -> left);
        invertTree(root -> right);
        return root;
    }
};

中序遍历：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) {
            return root;
        }

        invertTree(root -> left);

        TreeNode* tmp = root -> left;
        root -> left = root -> right;
        root -> right = tmp;

        // 上面遍历完左子树之后做了交换，所以这里要遍历的右子树是之前的左子树
        invertTree(root -> left);
        return root;
    }
};

后序遍历：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) {
            return root;
        }
        invertTree(root -> left);
        invertTree(root -> right);
        TreeNode* tmp = root -> left;
        root -> left = root -> right;
        root -> right = tmp;
        return root;
    }
};

层序遍历：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) {
            return root;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            TreeNode* tmp = node -> left;
            node -> left = node -> right;
            node -> right = tmp;
            if(node -> left) {
                q.push(node -> left);
            }
            if(node -> right) {
                q.push(node -> right);
            }
        }
        return root;
    }
};

8. 倒序层序遍历二叉树

层序遍历后再倒序：

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ret;
        if(root == nullptr) {
            return ret;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            auto size = q.size();
            // tmp 保存每一层的数据
            vector<int> tmp;
            for(int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                tmp.push_back(node -> val);
                if (node -> left) {
                    q.push(node -> left);
                }
                if (node -> right) {
                    q.push(node -> right);
                }
            }
            ret.push_back(tmp);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

9. 找前驱节点

前驱节点：中序遍历时的前一个节点
如果是二叉搜索树，前驱节点就是前一个比它小的节点（左子树最大的），即找左子树之后一路向右找

TreeNode* predecessor(TreeNode* node) {
  if(node == nullptr) {
    return null;
  }
  TreeNode* p = node -> left;
  if(p) {  // 左子树不为空，去左子树找前驱
    while(p -> right) {
      p = p -> right;
    }
    return p;
  }
  // 从祖父节点中找
  while(node -> parent && node == node -> parent -> left) { // 父节点不为空并且当前节点是父节点的左子节点
    node = node -> parent;
  }
  // node -> parent == null
  // node == node -> parent -> right
  return node -> parent;
}

10. 找后继节点

后继节点：中序遍历时的后一个节点
如果是二叉搜索树，后继节点就是后一个比它大的节点（右子树最小的），即找右子树之后一路向左找

TreeNode* sucessor(TreeNode* node) {
  if(node == nullptr) {
    return null;
  }
  TreeNode* p = node -> right;
  if(p) {  // 左子树不为空，去左子树找前驱
    while(p -> left) {
      p = p -> left;
    }
    return p;
  }
  // 从祖父节点中找
  while(node -> parent && node == node -> parent -> right) { // 父节点不为空并且当前节点是父节点的左子节点
    node = node -> parent;
  }
  return node -> parent;
}

11. N叉树前序遍历

递归写法：

class Solution {
public:
    vector<int> ret;
    void preNTree(Node* root, vector<int>& v) {
        if(root == nullptr) {
            return;
        }
        v.push_back(root -> val);
        int size = root -> children.size();
        for(int i = 0; i < size; i++) {
            Node* node = root -> children[i];
            if(node != nullptr) {
                preNTree(node, v);
            }
        }
    }
    vector<int> preorder(Node* root) {    
        if(root == nullptr) {
            return ret;
        }
        preNTree(root, ret);
        return ret;
    }
};

非递归写法：

class Solution {
public:
    vector<int> preorder(Node* root) {    
        if(root == nullptr) {
            return {};
        }
        stack<Node*> stk;
        vector<int> ret;
        stk.push(root);
        while(!stk.empty()) {
            Node* topNode = stk.top();
            stk.pop();
            ret.push_back(topNode -> val);
            reverse(topNode -> children.begin(), topNode -> children.end());
            for(Node* curNode : topNode -> children) {
                stk.push(curNode);
            }
        }
        return ret;
    }
};

12. N叉树后续遍历

非递归写法：

class Solution {
public:
    vector<int> postorder(Node* root) {    
        if(root == nullptr) {
            return {};
        }
        stack<Node*> stk;
        vector<int> ret;
        stk.push(root);
        while(!stk.empty()) {
            Node* topNode = stk.top();
            stk.pop();
            ret.insert(ret.begin(), topNode -> val);
            for(Node* curNode : topNode -> children) {
                if(curNode) {
                    stk.push(curNode);
                }  
            }
        }
        return ret;
    }
};

递归写法：

class Solution {
public:
    vector<int> ret;
    void postNTree(Node* root, vector<int>& v) {
        if(root == nullptr) {
            return;
        }
        int size = root -> children.size();
        for(int i = 0; i < size; i++) {
            Node* node = root -> children[i];
            if(node != nullptr) {
                postNTree(node, v);
            }
        }
        v.push_back(root -> val);
    }
    vector<int> postorder(Node* root) {    
        if(root == nullptr) {
            return ret;
        }
        postNTree(root, ret);
        return ret;
    }
};

13. N叉树的最大深度

非递归写法：

class Solution {
public:
    int maxDepth(Node* root) {
        vector<vector<int>> ret;
        if(root == nullptr) {
            return 0;
        }
        queue<Node*> q;
        q.push(root);
        while(!q.empty()) {
            auto size = q.size();
            vector<int> tmp;
            for(int i = 0; i < size; i++) {
                Node* node = q.front();
                q.pop();
                tmp.push_back(node -> val);
                for(int j = 0; j < node -> children.size(); j++) {   
                    q.push(node -> children[j]);
                }
            }
            ret.push_back(tmp);
        }
        return ret.size();
    }
};

递归写法：

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == nullptr) {
            return 0;
        }
        int result = 1;
        for (Node* child : root -> children) {
            result = max(result, 1 + maxDepth(child));
        }
        return result;
    }
};

14. 对称二叉树

递归写法：

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

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

非递归写法：

class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};