[Leetcode 94] 72 Binary Tree Inorder Traversal-白红宇

[Leetcode 94] 72 Binary Tree Inorder Traversal

阅读量：5094 次

发布时间：2019-06-13

本文共 3003 字，大约阅读时间需要 10 分钟。

Problem:

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

For example:

Given binary tree {1,#,2,3},

1    \     2    /   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Analysis:

Basic tree traversal problems. Recursive solution is just to proper arrange the visiting order of the tree. Iterative version need the help of stack. My own solution is that everytime pop a node from the stack, if it has no children nodes, then record it in the result vector. Else we must first push it right child node, then itself and at last its left child node. If any of the node is NULL, skip the pushing operation. Another thing to do is set the node's left and right pointer to NULL.

Code:

Recursive Version:

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
      
        res;13 14     vector
       
         inorderTraversal(TreeNode *root) {15         // Start typing your C/C++ solution below16         // DO NOT write int main() function17         res.clear();18         19         inorder(root);20         21         return res;22     }23     24     25 private:26     void inorder(TreeNode *node) {27         if (node == NULL)28             return ;29             30         inorder(node->left);31         res.push_back(node->val);32         inorder(node->right);33     }34 };

View Code

Iterative Version:

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
      
        inorderTraversal(TreeNode *root) {13         // Start typing your C/C++ solution below14         // DO NOT write int main() function15         vector
       
         res;16         17         if (root == NULL)18             return res;19         20         stack
        
          stk;21         TreeNode *tmp, *node;22         stk.push(root);23         do {24             node = stk.top();25             stk.pop();26             27             if (node->left == NULL && node->right == NULL) {28                 res.push_back(node->val);29                 continue;30             }31             32             if (node->right != NULL) {33                 stk.push(node->right);34                 node->right = NULL;35             }36             37             if (node->left != NULL) {38                 tmp = node->left;39                 node->left = NULL;40                 stk.push(node);41                 stk.push(tmp);42             } else 43                 stk.push(node);44             45         } while (!stk.empty());46         47         48         return res;49     }50 };

View Code

转载于:https://www.cnblogs.com/freeneng/p/3220947.html

你可能感兴趣的文章