leetcode 94. Binary Tree Inorder Traversal

Seawolf

1. Given a binary tree, return the inorder traversal of its nodes' values.
   
2. 
   
3. Example:
   
4. 
   
5. Input: [1,null,2,3]
   
6.    1
   
7.     \
   
8.      2
   
9.     /
   
10.    3
    
11. 
    
12. Output: [1,3,2]
    
13. Follow up: Recursive solution is trivial, could you do it iteratively?

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public List<Integer> inorderTraversal(TreeNode root) {
    
12.         List<Integer> list = new ArrayList<Integer>();
    
13.         if(root == null) return list;
    
14.         help(root,list);
    
15.         return list;
    
16.         
    
17.     }
    
18.     public void help(TreeNode root, List<Integer> list){
    
19.         if(root == null) return;
    
20.         
    
21.         if(root.left == null && root.right == null){
    
22.             list.add(root.val);
    
23.         }
    
24.         else if(root.left != null && root.right == null) {
    
25.             
    
26.             help(root.left, list);
    
27.             list.add(root.val);
    
28.         }
    
29.         else if(root.right != null && root.left == null){
    
30.             list.add(root.val);
    
31.             help(root.right,list);
    
32.         }
    
33.         else{
    
34.             
    
35.             help(root.left,list);
    
36.             list.add(root.val);
    
37.             help(root.right,list);
    
38.         }
    
39. }
    
40. }

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public List<Integer> inorderTraversal(TreeNode root) {
    
12.         List<Integer> list = new ArrayList<Integer>();
    
13.         
    
14.         Stack <TreeNode> stack = new Stack<>();
    
15.         TreeNode c = root;
    
16.         while(c != null || !stack.isEmpty()){
    
17.             while(c != null){
    
18.                
    
19.                 stack.push(c);
    
20.                 c = c.left;
    
21.             }
    
22.             c = stack.pop();
    
23.             list.add(c.val);
    
24.             c = c.right;
    
25.         }
    
26.         return list;
    
27.         
    
28.     }
    
29. 
    
30. }

复制代码