题解 | #JZ54 按之字形顺序打印二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
/*    TreeNode* node=nullptr;
    void traceTree(TreeNode *pRoot, int &k) {
        if (!pRoot) return;
        traceTree(pRoot->left, k);    //遍历左子树
        --k;    //当前节点为剩余最小值，计数递减
        if (k==0) node = pRoot;    //计数到，返回当前接地啊你
        else traceTree(pRoot->right, k);
    }
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        traceTree(pRoot, k);
        return node;
    } 
*/
    
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        TreeNode *node=pRoot;
        stack<TreeNode*> s;			
        
        while (node || s.size()) {
            while (node) {    //左子树到底
                s.push(node);
                node = node->left;
            }
            
            node = s.top();    //取出最左下节点
            s.pop();
            
            --k;    //遍历了最小节点，计数减1
            if (k==0) return node;    //计数为0 返回该节点
            
            node = node->right;    //
        }
        
        return nullptr;
    } 
};