首页 > 代码库 > [leetcode]_Binary Tree Inorder Traversal

[leetcode]_Binary Tree Inorder Traversal

2024-07-07 03:55:02   224人阅读

题目：二叉树的中序遍历。

思路：用递归来写中序遍历非常简单。但是题目直接挑衅说，----->"Recursive solution is trivial"。好吧。谁怕谁小狗。

 

递归代码：

 1     List<Integer> inOrder = new ArrayList<Integer>();
 2     
 3     public List<Integer> inorderTraversal(TreeNode root) {
 4         inOrderT(root);
 5         return inOrder;
 6     }
 7     
 8     public void inOrderT(TreeNode root){
 9         if(root != null){
10             inorderTraversal(root.left);
11             inOrder.add(root.val);
12             inorderTraversal(root.right);
13         }
14     }

 

循环解法：利用stack，由于中序遍历在访问完节点的左子树后访问节点值，因此，当前node ！= null时，将node 入栈，访问其左子树；当左子树为null了，从栈中弹出元素访问；再访问其右子树。

------>写的非常好的二叉树遍历的文章

 1     public List<Integer> inorderTraversal(TreeNode root) {
 2          
 3        List<Integer> inOrder = new ArrayList<Integer>();
 4        Stack<TreeNode> s = new Stack<TreeNode>();
 5        
 6        TreeNode help = root;
 7        while(help != null || !s.isEmpty()){
 8            while(help != null){
 9                s.push(help);
10                help = help.left;
11            }
12            if(!s.isEmpty()){
13                help = s.pop();
14                inOrder.add(help.val);
15                help = help.right;
16            }
17        }
18        
19        return inOrder;
20     
21     }

 


联系
我们