programming review (c++): (2)binary tree, BFS, DFS, recursive, non-recursive

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<<T->val;

            NLR(T->left);

            NLR(T->right);

    }

    return;

}

PS：

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

参数里，比如可以以此标记每个node的深度；

return，适合做累计操作，例子：

int maxDepth(TreeNode *root)    //求最大深度：反过来算+max，符合逻辑

{

    return root == NULL ?  : max(maxDepth(root -> left), maxDepth(root -> right)) + ;

}

参数里加&，贯穿型变量。

b.DFS/非递归先序

//DFS-非递归先序：中左右

void depthFirstSearch(TreeNode* root){

    stack<TreeNode *> nodeStack;  //stack

    nodeStack.push(root);

    TreeNode *node;

    while(!nodeStack.empty()){

        node = nodeStack.top();

        cout<<node->val;  //action

        nodeStack.pop();

        if(node->right!=null){

            nodeStack.push(node->right);

        }

        if(node->left!=null){

            nodeStack.push(node->left);

        }

    }

}

c.BFS

//BFS

void BFS(TreeNode* root){

    queue<TreeNode *> nodeQueue;  //queue

    nodeQueue.push(root);

    TreeNode *node;

    while(!nodeQueue.empty()){

        node = nodeQueue.front();

        cout<<node->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=;

        if(root){

            queue<TreeNode*> mq;

            mq.push(root);

            TreeNode* node;

            while(!mq.empty()){

                res++;

                for(int i=,n=mq.size();i<n;i++){

                    node=mq.front();

                    mq.pop();

                    if(node->left!=NULL)

                        mq.push(node->left);

                    if(node->right!=NULL)

                        mq.push(node->right);

                }

            }

        }

        return res;

    }

巴特西

programming review (c++): (2)binary tree, BFS, DFS, recursive, non-recursive

最新文章

热门文章