XingXing Park

[Leetcode 106] Construct Binary Tree from Inorder and Postorder Traversal

Posted on 2018-04-03 | In leetcode | Comments:

原题说明

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

解题思路

题目给出二叉树的中序遍历与后序遍历，要求重新构建原二叉树，返回根节点。

首先我们需要明确：

中序遍历的顺序：左、中、右
后序遍历的顺序：左、右、中

因此，我们知道后序遍历的最后一个元素是原二叉树的根节点，而此根节点将中序遍历分为了左子树的中序遍历与右子树的中序遍历。

根据以上思路，我们可以继续对左右子树的分别进行递归，直到序列为空，重构整个二叉树。

示例代码 (python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        dicinorder = {}
        for i, val in enumerate(inorder):
            dicinorder[val] = i
        start, end = 0, len(inorder)
        return self.helper(start, end, postorder, dicinorder)
    
    def helper(self, start, end, postorder, dicinorder):
        if start == end:
            return None
        root = TreeNode(postorder.pop())
        inorderIndex = dicinorder[root.val]
        root.right = self.helper(inorderIndex+1, end, postorder, dicinorder)
        root.left = self.helper(start, inorderIndex, postorder, dicinorder)
        return root

复杂度分析

我们使用一个字典记录inorder数组中value与对应index的关系，这样能快速查找每个value的index，每次查找时间复杂度为O(1)。
每个节点重构会被访问一次，一共n个节点。同时字典需要空间O(n)。所以复杂度分析为

时间复杂度: O(n)
空间复杂度: O(n)

归纳总结

此题要求重构二叉树，因此需要理解清楚中序遍历与后序遍历的定义。合理使用递归方法即可完成解题。

大家可以结合利用中序遍历与前序遍历构建二叉树这题，更好的理解问题：

[LeetCode 105] Construct Binary Tree from Preorder and Inorder Traversal

大家可以在 Tree Tag 中找到更多和树有关的内容。种香蕉树去了^_^

[Leetcode 250] Count Univalue Subtrees

Posted on 2018-04-03 | In leetcode | Comments:

原题说明

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

return 4.

解题思路

这题要求求出所有二叉树子树中，元素都相同的子树的个数。给出的例子中，以5为值得子树个数是4个，以1为值得子树个数是0，所以答案是4。

如果一个子树是满足条件的元素相同的子树，那以它的子节点为根的子树也一定是满足条件的元素相同的子树。因此，我们可以从叶子节点从下往上（bottom-up）判断。

如果两个以叶子节点为根的子树都是元素相同的子树，并且它们的值与父节点的值相同，则以父节点为根的子树也是满足条件的子树。但是节点没有父节点，无法往上判断，所以可以采用递归的方法从上往下调用判断。

在代码的实现过程中，这里我们用计数器self.count记录满足条件的子树个数，用一个辅助函数checkUni帮助我们从下往上查找UnivalSubTree

示例代码（python）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def countUnivalSubtrees(self, root):
        self.count = 0
        self.checkUni(root)
        return self.count

# If both children are "True" and root.val is equal to both children's values that exist, 
# then root node is uniValue subtree node. 
    def checkUni(self, root):
        if not root:
            return True
        l, r = self.checkUni(root.left), self.checkUni(root.right)
        if l and r and (not root.left or root.left.val == root.val) and \
        (not root.right or root.right.val == root.val):
            self.count += 1
            return True
        return False

复杂度分析

使用深度搜索DFS,每个节点被访问一次。并且递归过程中，递归栈的最大深度为O(n)。所以复杂度分析为:

时间复杂度 O(n)
空间复杂度：O(1), 递归栈深度O(n)

归纳总结：

递归方法解决树的问题。关键在于想明白父节点与子节点之间的关系。这里一个小点值得提醒，我们把空的节点判断为True, 这样方便于之后的计算。

大家可以在 Tree Tag 中找到更多和树有关的内容，在 Depth-first Search Tag 中找到更多和深度搜索相关的问题。

要种香蕉树去了：）

[Leetcode 112] Path Sum

Posted on 2018-04-03 | In leetcode | Comments:

原题说明

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

解题思路

本题给出一个数sum，要求判断二叉树中是否存在一条从根到叶root-to-leaf的路径，使得路径上数值的和等于sum。

事实上，如果存在这样一条路径，那么对于根节点的两个可能的子节点left和right, 两个中至少存在一条路径，使得从子节点left或者right到叶的路径的数值的和等于sum - root.val。以此类推，子节点的子节点亦是如此。

因此，我们自然想到利用递归，深度搜索的方法来解决此题。当搜索到叶节点时，如果叶节点的值val等于当时的sum,则找到了这样一条路径。

示例代码（python）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        if not root.left and not root.right: #当搜索到叶节点时
            return root.val == sum
        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

复杂度分析

使用深度搜索DFS,每个节点被访问一次。并且递归过程中，栈的最大深度为O(n)。考虑到本题并非平衡二叉树，最差将退化成链表，而大O代表复杂度的上阈值，因此为O(n)。
所以复杂度分析为：

时间复杂度： O(n)
空间复杂度：O(1), 递归栈深度O(n)

总结归纳：

这是一道典型的用递归方法解决的树的问题，采用深度搜索DFS的方法也是比较基础。

大家可以在 Tree Tag 中找到更多和树有关的内容，也可以在 Depth-first Search tag 中查找与深度搜索有关的题目。

不说了，忙着种香蕉树去了：）

[Leetcode 809] Expressive Words

Posted on 2018-04-03 | In leetcode | Comments:

原题说明

Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii". Here, we have groups, of adjacent letters that are all the same character, and adjacent characters to the group are different. A group is extended if that group is length 3 or more, so “e” and “o” would be extended in the first example, and “i” would be extended in the second example. As another example, the groups of “abbcccaaaa” would be “a”, “bb”, “ccc”, and “aaaa”; and “ccc” and “aaaa” are the extended groups of that string.

For some given string S, a query word is stretchy if it can be made to be equal to S by extending some groups. Formally, we are allowed to repeatedly choose a group (as defined above) of characters c, and add some number of the same character c to it so that the length of the group is 3 or more. Note that we cannot extend a group of size one like “h” to a group of size two like “hh” - all extensions must leave the group extended - ie., at least 3 characters long.

Given a list of query words, return the number of words that are stretchy.

Example:
Input:
S = “heeellooo”
words = [“hello”, “hi”, “helo”]
Output: 1
Explanation:
We can extend “e” and “o” in the word “hello” to get “heeellooo”.
We can’t extend “helo” to get “heeellooo” because the group “ll” is not extended.

Notes:

0 <= len(S) <= 100.
0 <= len(words) <= 100.
0 <= len(words[i]) <= 100.
S and all words in words consist only of lowercase letters
Read more »

[Leetcode 101] Symmetric Tree

Posted on 2018-04-02 | In leetcode | Comments:

原题说明

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following

Note:
Bonus points if you could solve it both recursively and iteratively.

解题思路

本题要求判断二叉树是否对称。简单来说，对一颗二叉树做镜像翻转，如果翻转后的二叉树与原树相同，即可判断为对称，反之则不对称。

我们可以用递归与非递归两种解法来完成这题，但总体思路上就是之前所说的。

在递归方法总是相对简单，我们使用深度搜索DFS来实现。用一个辅助函数helpcheck来完成对两棵树的同时遍历。这里我们只要对原本该遍历left的地方换成right,right的地方换成left,就完成了对镜像树的遍历。

在非递归方法中，我们使用广度搜索BFS来实现。使用双端队列来实现。每次从队列头部pop出两棵树的对应节点做判断，节点值不同，则返回False；如果满足条件，在把它们对应的左右子节点存入队尾。直到队列为空时，返回True

示例代码（递归 python）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.helpcheck(root, root)
    def helpcheck(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        return self.helpcheck(left.left, right.right) and self.helpcheck(left.right, right.left)

示例代码（递归 cpp）

/**
 * 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:
    bool checkHelper(TreeNode* left, TreeNode* right) {
        if (!left && !right) {
            return true;
        }
        if (!left || !right) {
            return false;
        }
        if (left->val != right->val) {
            return false;
        }
        return checkHelper(left->left, right->right) && checkHelper(left->right, right->left);
    }
    bool isSymmetric(TreeNode* root) {
        return checkHelper(root, root);
    }
};

示例代码（非递归 python）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

import collections
class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        q = collections.deque()
        q.extend([root,root])
        while q:
            tmpNode1 = q.popleft()
            tmpNode2 = q.popleft()
            if tmpNode1.val != tmpNode2.val:
                return False
            if tmpNode1.left and tmpNode2.right:
                q.extend([tmpNode1.left, tmpNode2.right])
            elif (tmpNode1.left and not tmpNode2.right) or (not tmpNode1.left and tmpNode2.right):
                return False
            if tmpNode1.right and tmpNode2.left:
                q.extend([tmpNode1.right, tmpNode2.left])
            elif (tmpNode1.right and not tmpNode2.left) or (not tmpNode1.right and tmpNode2.left):
                return False
        return True

示例代码（非递归 cpp）

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        TreeNode* left = root;
        TreeNode* right = root;
        stack<TreeNode*> nodeStackL;
        stack<TreeNode*> nodeStackR;
        while(left || !nodeStackL.empty()) {
            while(left) {
                if (!right) return false;
                if (left->val != right->val) return false;
                nodeStackL.push(left);
                nodeStackR.push(right);
                left = left->left;
                right = right->right;
            }
            if (right) return false;
            if(!nodeStackL.empty()) {
                left = nodeStackL.top();
                right = nodeStackR.top();
                nodeStackL.pop();
                nodeStackR.pop();
                left = left->right;
                right = right->left;
            }
        }
        if (right)  return false;
        return true;
    }
};

复杂度分析

对递归深度搜索，每个节点被访问一次，因此时间复杂度为O(n)。考虑到本题并非平衡二叉树，最差将退化成链表，递归栈最大深度为O(n)。因此其复杂度为：

时间复杂度： O(n)
空间复杂度：O(1), 递归栈深度O(n)

对非递归广度搜索，每个节点被访问一次，时间复杂度为O(n)。队的最大长度为其中最宽的层的节点数，因此空间复杂度仍然为O(n).

时间复杂度： O(n)
空间复杂度： O(n)

总结归纳：

本题想清楚树的对称的定义，便能利用深度搜索DFS和广度搜索BFS两种树的遍历的方法解题。类似的题目在实现的过程中一般都是利用这两种遍历方法，所以需要大家对树的遍历能够比较熟悉，以便加以利用。

之后我们还会添加一些相关的练习。同时大家可以在Tree Tag 中找到更多和树有关的内容。种香蕉树去了：）

[LeetCode 144] Binary Tree Preorder Traversal 二叉树前序遍历

[LeetCode 94] Binary Tree Inorder Traversal 二叉树中序遍历

[LeetCode 145] Binary Tree Postorder Traversal 二叉树后序遍历

[Leetcode 104] Maximum Depth of Binary Tree

Posted on 2018-04-01 | In leetcode | Comments:

原题说明

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3

解题思路

这题要求我们给出二叉树的最大深度。最大深度是指的从根节点一直到最远的叶节点中所有的节点数目。

因为二叉树有左右两棵，所以二叉树的最大深度为其根节点左右两棵子树中，最深的那棵子树的深度加一.

depth(root) = max(depth(root.left), depth(root.right)) + 1

显然我们可以用深度搜索（DFS）来实现这一算法，非常简单。

示例代码（python）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        ans = max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
        return ans

示例代码（c++）

/**
 * 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:
    int depthHelper(TreeNode* curr, int depth) {
        int left,right;
        if(!curr) {
            return depth;
        }
        left = depthHelper(curr->left, depth + 1);
        right = depthHelper(curr->right, depth + 1);
        return left > right ? left : right;
    }
    int maxDepth(TreeNode* root) {
        return depthHelper(root, 0);
    }
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1), 递归栈深度O(n)

总结归纳：

这题比较简单，想清楚树的深度的定义，找出递归的关系，就可以利用递归的方法解题。当然也可以使用非递归的方便遍历树来解决这一问题，有兴趣的朋友可以自己试试。

更多Tree相关的内容将更新在 Tree Tag，尽请期待，种香蕉树去了：）

[Leetcode 102] Binary Tree Level Order Traversal

Posted on 2018-03-31 | In leetcode | Comments:

原题说明

Given a binary tree, return the level order of its nodes’ values. (ie, from left to right, level by level).

For example:

Given binary tree [3,9,20,null,null,15,7],

return its level order traversal as:

[
 [3],
 [9,20],
 [15,7]
]

解题思路

本题要求层序遍历一个二叉树，与普通的广度遍历（Breadth First Search）稍有不同的是，需要按层分开。所以我们需要判断当前层的遍历是否结束。我们使用队queue来实现遍历，具体思路为：

建立一个队q,并将当前节点cur存入队中：
当前层的长度由变量count记录
如果队q非空：
- 2.1 建立一个空列tmplevel存放下一层的节点
- 2.2 如果count非零：
  - 当前节点cur更新为退队节点
  - 将当前节点cur的值存入列tmplevel中
  - count减1
  - 如果当前节点cur的左子节点非空，存入队q
  - 如果当前节点cur的右子节点非空，存入队q
  - 回到步骤2.2
- 2.3 将列tmplevel存入答案列ans
- 2.4 更新count为当前队列q长度
返回ans

算法过程中，我们用变量count追踪当前层剩余的未访问节点的个数，从而判断何时按层分开。思路还是比较简单的。

示例代码（python版）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        ans = []
        cur = root
        q = collections.deque([cur])
        count = len(q)
        while q:
            tmplevel = []
            while count:
                cur = q.popleft()
                tmplevel.append(cur.val)
                count -= 1
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            ans.append(tmplevel)
            count = len(q)
        return ans

复杂度分析

每个节点被访问一次，因此时间复杂度为O(n)。另一方面，队的最大长度为其中最宽的层的节点数，因此空间复杂度仍然为O(n).

时间复杂度： O(n)
空间复杂度： O(n)

总结归纳：

层序遍历level order也是树遍历的一种方法，结合我们之前讨论过的前序preorder、中序inorder、后序postorder遍历，希望大家能体会它们实现过程中的区别。

层序遍历使用队列queue这一数据结构实现，这点和前序preorder、中序inorder、后序postorder遍历是不同的。同时，层序遍历的空间复杂度大于另外三种深度遍历的复杂度，这点也值得我们注意。

[Leetcode 145] Binary Tree Postorder Traversal

Posted on 2018-03-30 | In leetcode | Comments:

原题说明

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:

Given binary tree [1,null,2,3],

return [3,2,1].

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

解题思路

深度遍历二叉树（DFS），可以分为

前序遍历（preorder）
中序遍历（inorder）
后序遍历（postorder）

这题要求使用后序遍历。后序遍历按照左子节点（left），右子节点（right），根节点（root）的顺序深度遍历二叉树。

同样，我们可以使用递归与非递归两种方法来实现前序遍历。递归的方法还是比较简单，参看相关代码就能明白。后序遍历的非递归的方法相比前序遍历与中序遍历而言，相对比较复杂，每个根节点我们都要visit两次，逻辑上需要大家仔细思考。

我们依然可以通过栈（stack）实现，总体思想为方位左子节点，直到其为空，同时将访问过得节点和其右子节点存入栈中。当退回是需要判断节点的右子节点是否为空，从而可以确定是否访问该节点还是访问该节点的右子节点：

使用栈（stack），每次visit当前节点node，同时如果当前节点的右子节点非空，将此右子节点存入栈中。然后将当前节点node压入栈中，并将当前节点更新为其左子节点，知道当前节点node为空。

之后当栈非空，如果栈顶元素的右子节点不等于该元素退栈后的栈顶元素，则将栈顶元素存入答案数组，退栈，并将当前节点node设为空。反之，交换栈顶的两个节点，并将当前节点设为栈顶元素，并退栈。

重复上述两个步骤，直到遍历完整棵二叉树。具体流程为：

建立一个空栈stack
如果当前节点node非空或者栈stack非空：
- 2.1 如果当前节点node非空：
  - 如果当前节点的右子节点非空：将右子节点存入栈中
  - 将当前节点node压入栈
  - 更新当前节点node为它的左子节点，回到步骤2.1
- 2.2 如果栈非空:
  - 将当前节点node设为栈顶元素并退栈
  - 如果栈非空并且栈顶元素等于当前节点的右子节点：
    交换当前节点和栈顶元素。反之访问并将当前节点node存入答案数组ans, 并将当前节点设为空
  - 回到步骤2

示例代码（递归 python版）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        def postorderhelper(root, ans):
            if root:
                postorderhelper(root.left, ans)
            else:
                return
            postorderhelper(root.right, ans)
            ans.append(root.val)
        ans = []
        postorderhelper(root, ans)
        return ans

示例代码（递归 c++版）

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

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

示例代码（非递归 python版）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        cur = root
        stack = collections.deque()
        ans = []
        while(cur or stack):
            while cur:
                if cur.right:
                    stack.append(cur.right)
                stack.append(cur)
                cur = cur.left
            if stack:
                cur = stack.pop()
                if stack and cur.right == stack[-1]:
                    tmp = stack.pop()
                    stack.append(cur)
                    cur = tmp
                else:
                    ans.append(cur.val)
                    cur = None
        return ans

示例代码（非递归 c++版）

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> nodeStack;
        stack<bool> stackLR; // False for Only Visited Left, True for Visited Left and Right
        bool lr = false;
        TreeNode* curr = root;
        while(curr || !stackLR.empty()){
            if(curr) {
                while(curr->left) {
                    nodeStack.push(curr);
                    stackLR.push(false);
                    curr = curr->left;
                }
                nodeStack.push(curr);
                stackLR.push(true);
                curr = curr->right;
                continue;
            }
            curr = nodeStack.top();
            nodeStack.pop();
            lr = stackLR.top();
            stackLR.pop();
            if (lr) {
                ret.push_back(curr->val);
                curr = NULL;
                
            } else {
                nodeStack.push(curr);
                stackLR.push(true);
                curr = curr->right;
            }
        }
        return ret;
    }
};

复杂度分析

对递归方法，每个节点都被访问一次，考虑到本题并非平衡二叉树，最差将退化成链表，递归栈最大深度为O(n)。所以复杂度分析为：

时间复杂度： O(n)
空间复杂度：O(1), 递归栈深度O(n)

对非递归方法，同样每个节点都被访问一次，考虑到本题并非平衡二叉树，最差将退化成链表，栈最大深度为O(n)。所以复杂度分析为：

时间复杂度： O(n)
空间复杂度：O(n)

总结归纳：

今天我们讲了二叉树的后序遍历，结合之前我们介绍的前序遍历、中序遍历，希望能对感兴趣的朋友有所帮助。

后序遍历的非递归实现相对前序遍历、中序遍历而言复杂一点，但只要逻辑上清晰，严格按照后序遍历的定义去做，也不难实现。

[Leetcode 94] Binary Tree Inorder Traversal

Posted on 2018-03-30 | In leetcode | Comments:

原题说明

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

For example:

Given binary tree [1,null,2,3],

return [1,3,2].

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

解题思路

深度遍历二叉树（DFS），可以分为

前序遍历（preorder）
中序遍历（inorder）
后序遍历（postorder）

这题要求使用中序遍历。中序遍历按照左子节点（left），根节点（root），右子节点（right）的顺序深度遍历二叉树。

同样，我们可以使用递归与非递归两种方法来实现前序遍历。递归的方法比较简单，参看相关代码就能明白。非递归的方法可以通过栈（stack）实现：

使用栈（stack），每次visit当前节点node，同时如果当前节点的右子节点非空，将此右子节点存入栈中，再将当前节点node更新为当前节点的左子节点。直到遍历完整棵二叉树。具体步骤为：

建立一个空栈stack
如果当前节点node非空或者栈stack非空：
- 2.1 如果当前节点node非空：
  - 将当前节点node压入栈
  - 更新当前节点node为它的左子节点，回到步骤2.1
- 2.2 如果栈非空，:
  - 将当前节点更新为栈顶元素，并且退栈
  - 访问当前节点
  - 更新当前节点node为它的右子节点，回到步骤2

示例代码（递归 python版）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def inorderhelper(self, root, ans):
        if root is None:
	        return
        self.inorderhelper(root.left, ans)  
        ans.append(root.val)
        self.inorderhelper(root.right, ans)
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """ 
        res = []
        self.inorderhelper(root, res)
        return res

示例代码（递归 cpp版）

 struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
 
class Solution {
public:
    void inorderHelper(TreeNode* curr, vector<int> &ret) {
        if (!curr) {
	    return;
	}
        inorderHelper(curr->left, ret);
        ret.push_back(curr->val);
        inorderHelper(curr->right, ret);
        return;
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        inorderHelper(root, ret);
        return ret;
    }
};

示例代码（非递归 python版）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = collections.deque()
        cur, ans = root, []
        while(cur or stack):
            while cur:
                stack.append(cur)
                cur = cur.left
            if stack:
                cur = stack.pop()
                ans.append(cur.val)
                cur = cur.right
        return ans

示例代码（非递归 cpp版）

 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> ret;
        TreeNode* curr = root;
        stack<TreeNode*> nodeStack;
        while(curr || !nodeStack.empty()){
            while(curr) {
                nodeStack.push(curr);
                curr = curr->left;
            }
            curr = nodeStack.top();
            nodeStack.pop();
            ret.push_back(curr->val);
            curr = curr->right;
        }
        return ret;
    }
};

复杂度分析

对递归方法，每个节点都被访问一次，考虑到本题并非平衡二叉树，最差将退化成链表，递归栈最大深度为O(n)。所以复杂度分析为：

时间复杂度： O(n)
空间复杂度：O(1), 递归栈深度O(n)

对非递归方法，同样每个节点都被访问一次，考虑到本题并非平衡二叉树，最差将退化成链表，栈最大深度为O(n)。所以复杂度分析为：

时间复杂度： O(n)
空间复杂度：O(n)

总结归纳：

今天我们讲了二叉树的中序遍历，结合之前我们介绍的前序遍历，希望能对感兴趣的朋友有所帮助。

这里再介绍一个小知识点，当二叉树(Binary Tree)为二叉搜索树（Binary Search Tree）时，中序遍历会按照节点值从小到大排列。因此这也提供给我们一个判断二叉树(Binary Tree)是否是二叉搜索树（Binary Search Tree）的方法。

[Leetcode 144] Binary Tree Preorder Traversal

Posted on 2018-03-30 | In leetcode | Comments:

原题说明

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:

Given binary tree [1,null,2,3],

return [1,2,3].

解题思路

深度遍历二叉树（DFS），可以分为

前序遍历（preorder）
中序遍历（inorder）
后序遍历（postorder）

这题要求使用前序遍历。前序遍历简单是说总是按照根节点（root），左子节点（left），右子节点（right）的顺序深度遍历二叉树。

我们可以使用递归与非递归两种方法来实现前序遍历。递归的方便比较简单，参看相关代码就能明白。这里主要讲一下非递归的方法：

建立一个空栈stack
如果当前节点node非空或者栈stack非空：
- 2.1 如果当前节点node非空：
  - 访问当前节点node
  - 如果当前节点的右子节点非空，压入栈
  - 更新当前节点node为它的左子节点，回到步骤2.1
- 2.2 如果栈非空，将当前节点更新为栈顶元素，并且退栈，回到步骤2

示例代码（递归 python版）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans = []
        self.preorderHelper(root, ans)
        return ans
    
    def preorderHelper(self, root, ans):
        if root:
            ans.append(root.val)
            self.preorderHelper(root.left, ans)
            self.preorderHelper(root.right, ans)

示例代码（非递归 python版）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        ans = []
        stack = collections.deque()
        while stack or root:
            while root :
                ans.append(root.val)
                if root.right:
                    stack.append(root.right)
                root = root.left
            if stack:
                root = stack.pop()
        return ans

复杂度分析

对递归方法，每个节点都被访问一次，考虑到本题并非平衡二叉树，最差将退化成链表，递归栈最大深度为O(n)。所以复杂度分析为：

时间复杂度： O(n)
空间复杂度：O(1), 递归栈深度O(n)

对非递归方法，同样每个节点都被访问一次，考虑到本题并非平衡二叉树，最差将退化成链表，栈最大深度为O(n)。所以复杂度分析为：

时间复杂度： O(n)
空间复杂度：O(n)

总结归纳：

树的遍历是对树的基本操作之一。今天我们讲了前序遍历。
相关的练习还有：

[LeetCode 94] Binary Tree Inorder Traversal 二叉树中序遍历

[LeetCode 145] Binary Tree Postorder Traversal 二叉树后序遍历

[LeetCode 102] Binary Tree Level Order Traversal 二叉树层序遍历

之后我们会继续讨论更多Tree相关的内容,并更新在 Tree Tag，尽请期待，种香蕉树去了：）

猩猩的乐园

技术面试问题详解

RSS

原题说明

解题思路

示例代码 (python)

复杂度分析

归纳总结

原题说明

解题思路

示例代码 （python）

复杂度分析

归纳总结：

原题说明

解题思路

示例代码 （python）

复杂度分析

总结归纳：

原题说明

原题说明

解题思路

示例代码 （递归 python）

示例代码 （递归 cpp）

示例代码 （非递归 python）

示例代码 （非递归 cpp）

复杂度分析

总结归纳：

原题说明

解题思路

示例代码 （python）

示例代码 （c++）

复杂度分析

总结归纳：

原题说明

解题思路

示例代码 （python版）

复杂度分析

总结归纳：

原题说明

解题思路

示例代码 （递归 python版）

示例代码 （递归 c++版）

示例代码 （非递归 python版）

示例代码 （非递归 c++版）

复杂度分析

总结归纳：

原题说明

解题思路

示例代码 （递归 python版）

示例代码 （递归 cpp版）

示例代码 （非递归 python版）

示例代码 （非递归 cpp版）

复杂度分析

总结归纳：

原题说明

解题思路

示例代码 （递归 python版）

示例代码 （非递归 python版）

复杂度分析

总结归纳：

示例代码（python）

示例代码（python）

示例代码（递归 python）

示例代码（递归 cpp）

示例代码（非递归 python）

示例代码（非递归 cpp）

示例代码（python）

示例代码（c++）

示例代码（python版）

示例代码（递归 python版）

示例代码（递归 c++版）

示例代码（非递归 python版）

示例代码（非递归 c++版）

示例代码（递归 python版）

示例代码（递归 cpp版）

示例代码（非递归 python版）

示例代码（非递归 cpp版）

示例代码（递归 python版）

示例代码（非递归 python版）