Skip to content

Latest commit

 

History

History
256 lines (219 loc) · 5.99 KB

94.Binary_Tree_Inorder_Traversal.md

File metadata and controls

256 lines (219 loc) · 5.99 KB
Raw
  1. Binary Tree Inorder Traversal

简单 https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

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

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

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

相关企业

  • 亚马逊 Amazon|6
  • 微软 Microsoft|6
  • 字节跳动|5
  • 苹果 Apple|3
  • 谷歌 Google|2

相关标签

  • Stack
  • Tree
  • Depth-First Search
  • Binary Tree

相似题目

  • Validate Binary Search Tree 中等
  • Binary Tree Preorder Traversal 简单
  • Binary Tree Postorder Traversal 简单
  • Binary Search Tree Iterator 中等
  • Kth Smallest Element in a BST 中等
  • Closest Binary Search Tree Value II 困难
  • Inorder Successor in BST 中等
  • Convert Binary Search Tree to Sorted Doubly Linked List 中等
  • Minimum Distance Between BST Nodes 简单

Recursive solution O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
    
        result = list()
        self.__inorderTraversal(root, result) 
        return result
        
    def __inorderTraversal(self, node, result):  # __funcname for private func
        if not node:
            return

        self.__inorderTraversal(node.left, result)
        result.append(node.val)
        self.__inorderTraversal(node.right, result)

注意上下两个的区别：(return)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
    
        result = list()
        return self.__inorderTraversal(root, result)
        
    def _inorderTraversal(self, node, result):
        if not node:
            return

        self.__inorderTraversal(node.left, result)
        result.append(node.val)
        self.__inorderTraversal(node.right, result)
        return result
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null){
            return result;
        }
        this.inorderTraversalRecursive(root, result);
        return result;
    }
    private void inorderTraversalRecursive(TreeNode node, List<Integer> result){
        if (node == null){
            return; 
        }

        this.inorderTraversalRecursive(node.left, result);
        result.add(node.val);
        this.inorderTraversalRecursive(node.right, result);
    }
}

更简洁版本（但是引用传递体现不明显）：more concise but not obvious recursion

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = list()
        if not root:
            return result

        result.extend(self.inorderTraversal(root.left))
        result.append(root.val)
        result.extend(self.inorderTraversal(root.right))
        return result
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null){
            return result;
        }
        result.addAll(this.inorderTraversal(root.left));
        result.add(root.val);
        result.addAll(this.inorderTraversal(root.right));
        return result;
    }
}

Solution 2: Use stack

先把最左边全都加进stack，然后开始pop，每pop一次检查：1.右边为空就一直pop； 2.不为空就去右边，然后再一次将左边的一条下来全加进stack里。重复该过程。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode currNode = root;

        while (currNode != null || !stack.empty()){
            while (currNode != null){
                stack.push(currNode);
                currNode = currNode.left;
            }

            currNode = stack.pop();
            result.add(currNode.val);
            currNode = currNode.right;
        }
        return result;
    }
}