1.二叉树定义

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

 

2.遍历

a.递归先序：

//递归先序: 中左右。PS：中序-左中右，后序-左右中，调换cout的位置即可void NLR(TreeNode* T){    if(T!=NULL){　　　   cout<
     
      val;                NLR(T->left);            NLR(T->right);    }    return;  }
     

 PS：

递归变量传递的几种方式：

• 参数里，比如可以以此标记每个node的深度；
• return，适合做累计操作，例子：
  int maxDepth(TreeNode *root)    //求最大深度：反过来算+max，符合逻辑{    return root == NULL ? 0 : max(maxDepth(root -> left), maxDepth(root -> right)) + 1;}
• 参数里加&，贯穿型变量。

b.DFS/非递归先序

//DFS-非递归先序：中左右void depthFirstSearch(TreeNode* root){    stack
     
       nodeStack;  //stack    nodeStack.push(root);    TreeNode *node;    while(!nodeStack.empty()){        node = nodeStack.top();        cout<
      
       val;  //action        nodeStack.pop();        if(node->right!=null){            nodeStack.push(node->right);           }        if(node->left!=null){            nodeStack.push(node->left);           }    }}
      
     

 c.BFS

//BFSvoid BFS(TreeNode* root){    queue
     
       nodeQueue;  //queue    nodeQueue.push(root);    TreeNode *node;    while(!nodeQueue.empty()){        node = nodeQueue.front();        cout<
      
       val;  //action        nodeQueue.pop();        if(node->left!=null){            nodeQueue.push(node->left);           }        if(node->right!=null){            nodeQueue.push(node->right);           }    }}
      
     

变形，按层action：

int maxDepth(TreeNode* root) {        int res=0;        if(root){            queue
     
       mq;            mq.push(root);            TreeNode* node;            while(!mq.empty()){                res++;                                for(int i=0,n=mq.size();i
      
       left!=NULL)                        mq.push(node->left);                    if(node->right!=NULL)                        mq.push(node->right);                }                            }        }        return res;    }