94.Binary Tree Inorder Traversal

再帰的なコードは以前のデータ構造書でよく見られたものです.

    public ArrayList inorderTraversal(ConstructBinaryTreefromPostorderandInorderTraversal.TreeNode root) {
        ArrayList res = new ArrayList<>();
        dfs(res, root);
        return res;
    }

    private void dfs(List res, ConstructBinaryTreefromPostorderandInorderTraversal.TreeNode node) {
        if (node == null) return;
        dfs(res, node.left);
        res.add(node.val);
        dfs(res, node.right);
    }

再帰的ではなく、Stckシミュレーションで順番を巡るので、理解してください.while条件とwhile中のifに注意してください.

public class Solution {
        public ArrayList inorderTraversal(TreeNode root) {
            ArrayList res = new ArrayList<>();
            LinkedList stack = new LinkedList<>();
            //  while    
            while (root != null || !stack.isEmpty()){
                if (root!=null){
                    stack.push(root);
                    root = root.left;
                }else {
                    root = stack.pop();
                    res.add(root.val);
                    root = root.right;
                }
            }
            return res;
        }
}

MAR 25 THこの問題は今日98.Validate Binary Search Treeを復習しに来ました.また忘れました.なぜwhileの中ではなく?を使うべきかと考えていた覚えがあります.
この問題はこのように書いてもいいです.

public List inorderTraversal(TreeNode root) {
    List list = new ArrayList<>();
    if(root == null) return list;
    Stack stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;
        
    }
    return list;
}

JULY 29 REVIEW
また繰り返しの方法を見ましたが、まだ書けません.上のコードは2つのwhileサイクルがはっきりしていますが、root=root.rightのところはまだ考えにくいです.あとは外の階のwhileです.二つの状況です.1はrootです!=nullの場合、このほうがよく考えられます.初めて入る時です.2はroot==nullの場合、statckは空ではなく、dfsがスタックの一番下に来る場合です.