树遍历
程序员文章站
2022-05-19 19:53:35
...
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null || !stack.empty()){
while(cur!=null){
stack.add(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
先往左走到最底,利用stack慢慢把堆里面的节点抛出来处理,内层的while中处理左节点,内层的非while抛出右边节点处理