LeetCode - 94. 二叉树的中序遍历 Swift &

给定一个二叉树，返回它的中序 遍历。

示例:

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法

swift

• 递归

/**
     递归算法
     官方题解：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode/
     时间复杂度为O(n)
     空间复杂度为O(n)
     */
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var result = [Int]()
        if root != nil {
            helper(root!, &result)
        }
        return result
    }
    
    func helper(_ root: TreeNode, _ result: inout [Int]) {
        // 左
        if root.left != nil {
            helper(root.left!, &result)
        }
        // 中
        result.append(root.val)
        // 右
        if root.right != nil {
            helper(root.right!, &result)
        }
    }

• 栈

/**
     栈
     
     参考题解：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/die-dai-fa-by-jason-2/
     作者：jason-2
     每到一个节点 A，因为根的访问在中间，将 A 入栈。然后遍历左子树，接着访问 A，最后遍历右子树。
     在访问完 A 后，A 就可以出栈了。因为 A 和其左子树都已经访问完成。
     
     时间复杂度为O(n)
     空间复杂度为O(n)
     */
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var result = [Int]()
        var stack = [TreeNode]()
        var current = root
        while current != nil || !stack.isEmpty {
            // 当前节点不为nil，入栈，移动到左节点
            while current != nil {
                stack.append(current!)
                current = current?.left
            }
            // 没有子节点了，出栈当前节点(父节点)
            current = stack.popLast()
            result.append(current!.val)
            // 移动到右节点
            current = current?.right
        }
        
        return result
    }

java

• 递归

class Solution {
    /**
     * 递归
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        helper(root, result);
        return result;
    }

    public void helper(TreeNode node, List result) {
        if (node == null) {
            return;
        }
        helper(node.left, result);
        result.add(node.val);
        helper(node.right, result);
    }
}

• 迭代

/**
     * 迭代
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return result;
        }
        // 左中右
        TreeNode current = root;
        while (!stack.isEmpty() || current != null) {
            // 一直向左节点移动，直到最左边的节点
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            // 没有左节点，出当前节点(父节点)
            current = stack.pop();
            result.add(current.val);
            // 向右节点移动
            current = current.right;
        }
        return result;
    }

GitHub：https://github.com/huxq-coder/LeetCode
欢迎star