145. 二叉树的后序遍历

[dutLyuyu]

145. 二叉树的后序遍历

思路

用栈模拟递归

实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// var postorderTraversal = function(root) {
//     const result = [];
//     const loop = (node) => {
//         if (!node) return;
//         if (node.left) loop(node.left);
//         if (node.right) loop(node.right);
//         result.push(node.val);
//     }
//     loop(root)
//     return result;
// };

var postorderTraversal = function(root) {
    if (!root) return [];
    const stack1 = [root];
    const stack2 = [0];
    const result = [];
   while(stack1.length !== 0){
       const node = stack1[stack1.length - 1];
       const status = stack2[stack2.length - 1];
       switch(status) {
           case 0: 
             stack2[stack2.length - 1] = 1;
             if (node.left) {
                 stack1.push(node.left);
                 stack2.push(0);
             }
             break;
           case 1:
             stack2[stack2.length - 1] = 2;
             if (node.right) {
                 stack1.push(node.right);
                 stack2.push(0);
             }
             break;
            case 2:
              result.push(node.val);
              stack1.pop();
              stack2.pop();
              break;
            default:
             break; 
       }
   }
   return result;
};