LeetCode : Binary Tree Inorder Traversal 二叉树中序遍历递归迭代

傷城~ 2021-06-24 16:10 286阅读 0赞

**试题：**  
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?  
**代码：**  
递归

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        List<Integer> out = new ArrayList<>();
        public List<Integer> inorderTraversal(TreeNode root) {
            if(root == null) return out;
            inorderTraversal(root.left);
            out.add(root.val);
            inorderTraversal(root.right);
            return out;
        }
    }

迭代

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> out = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            
            TreeNode cur = root;
            while(cur!=null || !stack.isEmpty()){  //有时出现cur = tmp.right非null，但stack为空的情况。
                
                while(cur!=null){
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode tmp = stack.pop();
                out.add(tmp.val);
                cur = tmp.right;
                
            }
            return out;
    
        }
    }