LeetCode – Binary Tree Inorder Traversal

题目:

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

Example:

Input:

 [1,null,2,3]
   1
    \
     2
    /
   3

Output:

 [1,3,2]

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

解题:

树的中序遍历:

  1. 如果当前节点的左孩子为空,则输出当前节点并将其右孩子作为当前节点。
  2. 如果当前节点的左孩子不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
    a) 如果前驱节点的右孩子为空,将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
    b) 如果前驱节点的右孩子为当前节点,将它的右孩子重新设为空(恢复树的形状)。输出当前节点。当前节点更新为当前节点的右孩子。
  3. 重复以上1、2直到当前节点为空。

实现:

  • 递归方式:

对左子结点调用递归函数,根节点访问值,右子节点再调用递归函数

/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector <int> res;
        inorder(root, res);
        return res;
        
    }
    void inorder(TreeNode *root, vector<int> &res){
        if (!root) {
            return;
        }
        if (root->left) {
            inorder(root->left, res);
        }
        res.push_back(root->val);
        if (root->right){
            inorder(root->right, res);
        }
    }
};
空间复杂度:O(n),
时间复杂度:O(n)。
  • 使用栈实现

         从根节点开始,先将根节点压入栈,然后再将其所有左子结点压入栈,然后取出栈顶节点,保存节点值,再将当前指针移到其右子节点上,若存在右子节点,则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右,

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
       vector<int> res;
       stack<TreeNode*> ss;
       TreeNode *p= root;
        
       while(!ss.empty()||p){
           if (p){
               ss.push(p);
               p = p->left;
           }
           else {
               p=ss.top();
               ss.pop();
               res.push_back(p->val);
               p= p->right;
           }
       }
       return res;
        
    }
};
空间复杂度:O(n),
时间复杂度:O(n)。

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注